句容本地网站,中心网站建设方法,百度图片查找,oa系统手机端来源#xff1a;牛客网#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 一个弹球#xff08;可视为质点牛客网
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 一个弹球可视为质点被水平抛出落地时发生完全弹性碰撞设弹球第一次落地位置为x则第i次落地位置为(2i-1)x 若弹球第一次落地的位置在区间[L,R]均匀随机分布求弹球落在区间[L,R]内的总次数的数学期望值 可以证明答案为有理数若答案表示为最简分数为a/b则存在c使得bc mod 998244353 1 只需输出ac mod 998244353 输入描述: 第一行一个整数n 接下来n行每行两个空格分隔的整数L,R 输出描述: 输出n行每行一个整数表示a*c mod 998244353 示例1 输入
3
3 4
3 5
1 5输出
1
1
166374060备注:
n组询问1n50000
1LR10000000题解
期望推导过程 由题可得 E(k)a/b cinv(b) E(k)a * c % mod 关于逆元的具体求法看我其他博客
代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll MOD998244353;
const int maxn1e750;
ll inv[maxn],sum[maxn];
void init()
{inv[1]sum[1]1;for(int i 2; i maxn; i) {inv[i](-MOD/iMOD)*inv[MOD%i]%MOD;sum[i](sum[i-2]inv[i])%MOD;}
}
int main()
{init();int q;scanf(%d, q);while(q--){ll l,r;scanf(%lld%lld ,l,r);ll e(r/l1)/2;ll ans(sum[2*e-1]-l*inv[r]%MOD*e%MOD)%mod;ansans*r%MOD*inv[r-l]%MOD;ans(ans%MODMOD)%MOD;printf(%lld\n, ans);}
}
