Submit Info #49842

Problem Lang User Status Time Memory
$\sum_{i=0}^{\infty} r^i i^d$ cpp (anonymous) AC 970 ms 388.06 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.37 MiB
0_01 AC 568 ms 238.19 MiB
0_02 AC 943 ms 388.05 MiB
2_00 AC 574 ms 238.18 MiB
2_01 AC 575 ms 238.08 MiB
2_02 AC 681 ms 238.06 MiB
2_03 AC 704 ms 242.80 MiB
2_04 AC 970 ms 388.05 MiB
2_05 AC 941 ms 388.06 MiB
example_00 AC 602 ms 238.07 MiB

#pragma GCC optimize("O3","Ofast","unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long const int p=998244353; const int maxn=1e7+5; int invmas[maxn]; int pomas[maxn]; bool used[maxn]; int lp[maxn]; vector <int> pr; int po(int a,int b) { if(b==0) return 1; if(b==1) return a; if(b%2==0) { int u=po(a,b/2); return (u*u)%p; } else { int u=po(a,b-1); return (a*u)%p; } } int inv(int x) {return po(x,p-2);} pair <int,int> operator *(pair <int,int> u,int v) { u.first*=v;u.second*=v; u.first%=p;u.second%=p; return u; } pair <int,int> operator +(pair <int,int> u,pair<int,int> v) { u.first+=v.first;u.second+=v.second; u.first%=p;u.second%=p; return u; } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int r,d; cin>>r>>d; if(r==0 && d==0) {cout<<1;return 0;} invmas[0]=0;if(d!=0) pomas[0]=0; else pomas[0]=1; for(int i=1;i<maxn;++i) { if(lp[i]==0) { invmas[i]=inv(i); pomas[i]=po(i,d); lp[i]=i; if(i!=1) pr.push_back(i); } for(int j=0;j<pr.size() && pr[j]<lp[i] && i*pr[j]<maxn;++j) { int x=pr[j]*i; invmas[x]=(invmas[i]*invmas[pr[j]])%p; pomas[x]=(pomas[i]*pomas[pr[j]])%p; lp[x]=pr[j]; } } vector <pair<int,int> > v(d+2); v[0]={0,1}; int ir=inv(r); for(int i=1;i<=(d+1);++i) { v[i]=(v[i-1]*ir)+make_pair((pomas[i-1]*ir)%p,0); } pair <int,int> z={0,0}; int currc=1; for(int i=0;i<=(d+1);++i) { if(i%2==0) z=z+(v[i]*currc); else z=z+(v[i]*(p-currc)); currc*=(d-i+1); currc%=p; currc*=invmas[i+1]; currc%=p; } z.first%=p;z.first+=p;z.first%=p;z.second%=p;z.second+=p;z.second%=p; int ans=(-z.first*inv(z.second));ans%=p; int res=((-ans)%p+p)%p; cout<<res; return 0; }