代码

#include<iostream>
#include<cstdio>
using namespace std;
#define N 15000012
#define U 30000012
#define mod 998244353
inline int M(int x){return (x>=mod)?(x-mod):x;}
inline int M1(int x){return (x<0)?(x+mod):x;}
inline int ksm(int p,int k){int res=1;while(k){if(k&1)res=1ll*res*p%mod;k>>=1;p=1ll*p*p%mod;}return res;}
int n,m,R,fac[U],inv[N],f[U],ans=0;bool b[N];
int main(){
	fac[0]=1;for(int i=1;i<U;i++)fac[i]=1ll*fac[i-1]*i%mod;inv[N-1]=ksm(fac[N-1],mod-2);for(int i=N-2;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
//	scanf("%d%d%d",&n,&m,&R);
	m=n=1.5e7,R=1;int i,j,o;
	for(i=1;i<=m;i++)f[i]=1ll*fac[m-i+n-1]*inv[m-i]%mod;
	for(i=n>>1;i>=1;i--)f[i]=M(f[i]+f[i<<1]);
	for(j=3;j<=m;j+=2)if(!b[j]){for(i=min(m+1ll,1ll*j*j);i<=m;i+=j)b[i]=1;for(i=m/j;i>=1;i--)f[i]=M(f[i]+f[i*j]);}
	for(i=R+1;i<=n;i++)o=1ll*f[i]*inv[i]%mod*inv[n-i]%mod*fac[i-2]%mod*inv[i-R-1]%mod,((i-R)&1)?(ans=M1(ans-o)):(ans=M(ans+o));
	ans=(ans+1ll*f[1]*inv[n-1])%mod;ans=1ll*ans*n%mod*inv[R-1]%mod*ksm(1ll*fac[n+m-1]*inv[n-1]%mod*inv[m]%mod,mod-2)%mod;printf("%d",M(ans+R));return 0;
}

评测结果