Submit Info #49840

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

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.61 MiB
0_01 AC 758 ms 163.09 MiB
0_02 AC 1080 ms 315.96 MiB
2_00 AC 751 ms 163.09 MiB
2_01 AC 758 ms 163.09 MiB
2_02 AC 816 ms 163.21 MiB
2_03 AC 850 ms 170.71 MiB
2_04 AC 1125 ms 315.97 MiB
2_05 AC 1083 ms 315.97 MiB
example_00 AC 754 ms 163.09 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 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(!used[i]) { used[i]=true; invmas[i]=inv(i); pomas[i]=po(i,d); for(int j=2;i*j<maxn;++j) { if(!used[i*j] && used[j]) { invmas[i*j]=(invmas[i]*invmas[j])%p; pomas[i*j]=(pomas[i]*pomas[j])%p; used[i*j]=true; } } } } 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; }