Submit Info #5330

Problem Lang User Status Time Memory
$\sum_{i=0}^{\infty} r^i i^d$ cpp kyoprofriends AC 1459 ms 229.80 MiB

ケース詳細
Name Status Time Memory
0_00 AC 0 ms 0.68 MiB
0_01 AC 0 ms 0.67 MiB
0_02 AC 1328 ms 229.80 MiB
2_00 AC 0 ms 0.68 MiB
2_01 AC 2 ms 0.71 MiB
2_02 AC 2 ms 0.78 MiB
2_03 AC 54 ms 11.94 MiB
2_04 AC 1459 ms 229.80 MiB
2_05 AC 1315 ms 229.80 MiB
example_00 AC 0 ms 0.68 MiB

#include<stdio.h> #define ll long long #define rep(i,l,r)for(ll i=(l);i<(r);i++) ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;} #define invp(a,p)pom(a,p-2,p) #define MOD 998244353 ll inv[10000010]; void makeinv(int n,int mod){inv[1]=1;rep(i,2,n+1)inv[i]=inv[mod%i]*(mod-mod/i)%mod;} ll rr[10000010]; ll ss[10000010]; int main(){ ll r,d; scanf("%lld%lld",&r,&d); makeinv(d,MOD); ll ans=0,sum=0; rr[0]=1; rep(x,1,d+1)rr[x]=rr[x-1]*r%MOD; rep(x,0,d+1)ss[x]=rr[x]*pom(x,d,MOD)%MOD; rep(x,0,d+1)sum+=ss[x]; sum%=MOD; ll c=1; rep(k,0,d+1){ ans=(ans+(k%2?-1:1)*rr[k]*c%MOD*sum)%MOD; c=c*(d+1-k)%MOD*inv[k+1]%MOD; sum=(sum-ss[d-k])%MOD; } ans=ans*pom(1-r,MOD-1-(d+1),MOD)%MOD; printf("%lld\n",(ans+MOD)%MOD); }