( ext{Solution:})
考虑单位根反演。
[frac{1}{k}sum_{i=0}inom{n}{i}p^i(i-imod k)
\
ext{Part1:}
\
sum_{i=0}^n inom{n}{i}p^i i
\
=npsum_{i=0}^n inom{n-1}{i-1}p^{i-1}
\
=npsum_{j=0}^{n-1} inom{n-1}{j}p^j
\
=np(1+p)^{n-1}
\
ext{Part2:}
\
sum_{i=0}^n inom{n}{i}p^i(imod k)
\
=sum_{i=0}^n inom{n}{i}p^isum_{j=0}^{k-1} j[jequiv i(mod k)]
\
=sum_{i=0}^n inom{n}{i}p^isum_{j=0}^{k-1} j[k|i-j]
\
=sum_{i=0}^n inom{n}{i}p^isum_{j=0}^{k-1} jfrac{1}{k}sum_{l=0}^{k-1}omega_k^{l(i-j)}
\
=frac{1}{k}sum_{j=0}^{k-1} jsum_{l=0}^{k-1} omega_k^{-lj}sum_{i=0}^n inom{n}{i}p^iomega_k^{il}
\
=frac{1}{k}sum_{j=0}^{k-1} jsum_{l=0}^{k-1} omega_k^{-lj}(1+pomega_k^l)^n
\
=frac{1}{k}sum_{l=0}^{k-1}(1+pomega_k^l)^nsum_{j=0}^{k-1}jomega_k^{-lj}
\
=frac{1}{k}sum_{l=0}^{k-1}(1+pomega_k^l)^nsum_{j=0}^{k-1}jfrac{1}{(omega_k^l)^j}
]
后面是等差乘等比数列求和。
复杂度 (O(klog n).)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int g=3;
inline int Add(int x,int y){return (x+y)%mod;}
inline int Mul(int x,int y){return 1ll*x*y%mod;}
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=Mul(res,x);
x=Mul(x,x);y>>=1;
}
return res;
}
int n,p,k;
int P1,P2;
int num,len=1;
int pwk[1<<21];
inline int getinv(int x){return qpow(x,mod-2);}
signed main(){
scanf("%lld%lld%lld",&n,&p,&k);
P1=Mul(n,Mul(p,qpow((1+p)%mod,n-1)));
while(len<k)len<<=1,num++;
int Wk=qpow(g,(mod-1)/k);
pwk[0]=1;
for(int i=1;i<k;++i)pwk[i]=Mul(pwk[i-1],Wk);
for(int i=0;i<k;++i){
int s1=qpow(Add(1,Mul(p,pwk[i])),n);
int q=pwk[i];
q=getinv(q);
if(q==1)P2=Add(P2,Mul(s1,Mul(k,Mul(k-1,getinv(2)))));
else{
int pt1=Mul(k,qpow(q,k));
pt1=Mul(pt1,getinv(q-1));
int pt2=Mul(q,Add(mod-1,qpow(q,k)));
pt2=Mul(pt2,getinv(Mul(q-1,q-1)));
pt2=mod-pt2;
P2=Add(P2,Mul(Add(pt1,pt2),s1));
}
}
P2=Mul(P2,getinv(k));
P2=mod-P2;
P1=Add(P1,P2);
P1=Mul(P1,getinv(k));
printf("%lld
",P1);
return 0;
}