如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
我们有单位根反演：
\[[k\mid j]=\frac{1}{k}\sum\limits_{d=0}^{k-1}\omega_{k}^{dj}\]证明：
当 $k\mid j$ 时，$\omega_k^j=1$，右式 $=1$。
当 $k\nmid j$ 时，$\omega_k^j\neq 1$，右式 $=\frac{\omega_k^{kj}-\omega_k^{0j}}{\omega_k^j-1}=0$。
根据单位根反演：
\[\begin{aligned} &\sum\limits_{i=0}^n{n\choose i}p^i\left\lfloor\frac{i}{k}\right\rfloor\\ =&\sum\limits_{i=0}^n{n\choose i}p^i(\sum\limits_{j=0}^i[k\mid j]-1)\\ =&\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i[k\mid j]-\sum\limits_{i=0}^n{n\choose i}p^i\\ =&\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\frac{1}{k}\sum\limits_{d=0}^{k-1}\omega_{k}^{dj}-(p+1)^n\\ =&\frac{1}{k}\sum\limits_{d=0}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\omega_{k}^{dj}-(p+1)^n\\ =&\frac{1}{k}\sum\limits_{i=0}^n{n\choose i}p^i(i+1)+\frac{1}{k}\sum\limits_{d=1}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\omega_{k}^{dj}-(p+1)^n\\ \end{aligned}\]先算左边的东西：
\[\begin{aligned} &\sum\limits_{i=0}^n{n\choose i}p^i(i+1)\\ =&\sum\limits_{i=0}^n{n\choose i}p^ii+\sum\limits_{i=0}^n{n\choose i}p^i\\ =&\sum\limits_{i=0}^n{n-1\choose i-1}p^in+(p+1)^n\\ =&np\sum\limits_{i=0}^{n-1}{n-1\choose i}p^i+(p+1)^n\\ =&np(p+1)^{n-1}+(p+1)^n \end{aligned}\]然后是中间的东西：
\[\begin{aligned} &\sum\limits_{d=1}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\omega_{k}^{dj}\\ =&\sum\limits_{d=1}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\frac{\omega_{k}^{d(i+1)}-1}{\omega_{k}^{d}-1}\\ =&\sum\limits_{d=1}^{k-1}\frac{\sum\limits_{i=0}^n{n\choose i}p^i\omega_{k}^{d(i+1)}-\sum\limits_{i=0}^n{n\choose i}p^i}{\omega_{k}^{d}-1}\\ =&\sum\limits_{d=1}^{k-1}\frac{\omega_{k}^{d}\sum\limits_{i=0}^n{n\choose i}(p\omega_{k}^{d})^i-(p+1)^n}{\omega_{k}^{d}-1}\\ =&\sum\limits_{d=1}^{k-1}\frac{\omega_{k}^{d}(p\omega_{k}^{d}+1)^n-(p+1)^n}{\omega_{k}^{d}-1}\\ \end{aligned}\]所以原式等于：
\[\frac{1}{k}\left(np(p+1)^{n-1}+(p+1)^n+\sum\limits_{d=1}^{k-1}\frac{\omega_{k}^{d}(p\omega_{k}^{d}+1)^n-(p+1)^n}{\omega_{k}^{d}-1}\right)-(p+1)^n\]时间复杂度 $\mathrm O(k\log n)$，复杂度瓶颈是快速幂。
#include<cstdio>
int const mod=998244353;
int o,n,p,k,ans;
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
int main(){
scanf("%d%d%d",&n,&p,&k);
o=pow(3,(mod-1)/k);
for(int d=1,i=1;i<k;i++){
d=1ll*d*o%mod;
ans=(ans+(1ll*d*pow(1ll*p*d%mod+1,n)-pow(p+1,n)+mod)%mod*pow(d-1,mod-2))%mod;
}
ans=(ans+1ll*n*p%mod*pow(p+1,n-1)+pow(p+1,n))%mod*pow(k,mod-2)%mod;
ans=(ans-pow(p+1,n)+mod)%mod;
printf("%d\n",ans);
return 0;
}