wannafly 15 C、小球碰撞 (欧拉+快速幂求逆元)

题目链接：https://www.nowcoder.com/acm/contest/113/C

题意： 小球的初位置x可以在[L,R]上任意一点,他会弹跳掉到点（2i-1）x,问掉到[L,R]里的次数的期望值%998244353的值.

预处理F[t]有点难，我们需要求出5e6个数的逆元（快速矩阵幂logMod），会超时！
我们先将ji[t]（所有奇数的阶乘求出（表示(2t-1)!）),然后求出ji[5000001]的逆元ni[5000001]
一次遍历从大到小求出所有ji[t]的ni[t]（ji[t] = ji[t+1](2t)(2t+1)）!
后面再一次遍历：F[t] = F[t-1] + ni[t]ji[t-1]（2t-2）(得到1/（2t-1）的逆元）！

这道题将逆元的用法推广了一步！是道好题！

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#define llt long long
using namespace std;

const int Size = 6e6+70;
const llt Mod = 998244353;
//int p[Size];

llt quick_pow(llt x,llt a){
    if(a==0) return 1;
    if(a==1) return x;

    llt y = quick_pow(x,a/2);
    return (a%2==0)?(y*y%Mod):(y*y%Mod*x%Mod);
}
llt F[Size],ji[Size],ni[Size];

void init(){

    //求出所有奇数阶乘
    ji[1]=1;
    for(int i=3;i<=1e7+1;i+=2)
        ji[(i+1)/2]=ji[(i-1)/2]*(i-1)%Mod*i%Mod;

    ni[5000001] = quick_pow(ji[5000001],Mod-2);

    //求出奇数阶乘的逆元
    for(int i=1e7-1;i>=3;i-=2){
        ni[(i+1)/2] = (ni[(i+3)/2]*(i+1)%Mod*(i+2)%Mod);
    }

    //求出前i项1/i的逆元和
    F[1]=1;
    for(int i=3;i<=1e7+1;i+=2){
        F[(i+1)/2] = (F[(i-1)/2]+ni[(i+1)/2]*ji[(i-1)/2]%Mod*(i-1)%Mod)%Mod;
    }
}
int main(){
    init();
    int n;
    scanf("%d",&n);
    while(n--){
        int L,R;
        scanf("%d%d",&L,&R);
        llt ans = 1LL*R*quick_pow(R-L,Mod-2)%Mod;//R/(R-L)
        int t =R/L + ((R%L==0&&(R/L)%2==1)?0:2);
        ans = ans * ((F[(t-1)/2]+Mod-(t-1)/2*L%Mod*quick_pow(R,Mod-2)%Mod)%Mod)%Mod;
        printf("%lld\n",ans);
    }

}