Wannafly挑战赛25C 期望操作数

---

简单题啦

\(f[i]=\frac{\sum_{j<=i}f[j]}{i}+1\)

\(f[i]=\frac{f[i]}{i}+\frac{\sum_{j<i}f[j]}{i}+1\)

\(\frac{i-1}{i}f[i]=\frac{\sum_{j<i}f[j]+i}{i}\)

\(f[i]=\frac{\sum_{j<i}f[j]+i}{i-1}\)

一边求逆元一边dp即可

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 998244353

typedef long long ll;

il int gi(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

ll f[10000001],inv[10000001];

int T,l,r;

int main(){

#ifndef ONLINE_JUDGE

	freopen("197c.in","r",stdin);

	freopen("197c.out","w",stdout);

#endif

	f[0]=0;f[1]=2;ll S=0;inv[1]=1;

	for(int i=2;i<10000001;++i)f[i]=(1+(S+1)*inv[i-1])%mod,S=(S+f[i])%mod,inv[i]=(mod-(mod/i*inv[mod%i])%mod)%mod;

	T=gi();

	while(T--)l=gi(),r=gi(),printf("%lld\n",f[r-l+1]);

	return 0;

}