题面
一个比较纯粹的推式子题目，第一步先将整除拆开：
∑
i
=
0
n
(
n
i
)
p
i
1
k
(
i
−
i
m
o
d
k
)
\sum_{i=0}^n \binom{n}{i} p^i \frac{1}{k}(i-i \mod k)
∑i=0n(in)pik1(i−imodk)
拆开括号并枚举余数：
1
k
(
∑
i
=
0
n
(
n
i
)
p
i
i
−
(
n
i
)
p
i
∑
j
=
0
k
−
1
[
(
i
−
j
)
m
o
d
k
=
0
]
j
)
\frac{1}{k}(\sum_{i=0}^n \binom{n}{i} p^i i-\binom{n}{i}p^i \sum_{j=0}^{k-1}[(i-j)\mod k=0]j)
k1(∑i=0n(in)pii−(in)pi∑j=0k−1[(i−j)modk=0]j)
利用组合数公式以及单位根反演得：
1
k
(
∑
i
=
1
n
(
n
−
1
i
−
1
)
n
p
i
−
(
n
i
)
p
i
∑
j
=
0
k
−
1
j
k
∑
t
=
0
k
−
1
ω
k
t
(
i
−
j
)
)
\frac{1}{k}(\sum_{i=1}^n \binom{n-1}{i-1}n p^i-\binom{n}{i}p^i \sum_{j=0}^{k-1} \frac{j}{k} \sum_{t=0}^{k-1} \omega_k^{t(i-j)})
k1(∑i=1n(i−1n−1)npi−(in)pi∑j=0k−1kj∑t=0k−1ωkt(i−j))
根据二项式定理整理：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
j
=
0
k
−
1
j
∑
t
=
0
k
−
1
ω
k
−
t
j
∑
i
=
0
n
(
n
i
)
p
i
ω
k
t
i
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k} \sum_{j=0}^{k-1}j \sum_{t=0}^{k-1} \omega_k^{-tj} \sum_{i=0}^n \binom{n}{i} p^i \omega_k^{ti})
k1(np(p+1)n−1−k1∑j=0k−1j∑t=0k−1ωk−tj∑i=0n(in)piωkti)
再用二项式定理：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
j
=
0
k
−
1
∑
t
=
0
k
−
1
j
ω
k
−
t
j
(
p
ω
k
t
+
1
)
n
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k} \sum_{j=0}^{k-1} \sum_{t=0}^{k-1} j \omega_k^{-tj}(p \omega_k^t+1)^n)
k1(np(p+1)n−1−k1∑j=0k−1∑t=0k−1jωk−tj(pωkt+1)n)
根据这个式子的结构可以用任意模长DFT来求解，但又由于是等差乘等比的结构，可以使用特殊的方法：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
j
=
0
k
−
1
∑
t
=
0
k
−
1
(
p
ω
k
t
+
1
)
n
∑
i
=
0
j
−
1
ω
k
−
t
j
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k} \sum_{j=0}^{k-1} \sum_{t=0}^{k-1} (p \omega_k^t+1)^n\sum_{i=0}^{j-1} \omega_k^{-tj})
k1(np(p+1)n−1−k1∑j=0k−1∑t=0k−1(pωkt+1)n∑i=0j−1ωk−tj)
交换求和顺序：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
t
=
0
k
−
1
(
p
ω
k
t
+
1
)
n
∑
i
=
0
k
−
2
∑
j
=
i
+
1
k
−
1
ω
k
−
t
j
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k} \sum_{t=0}^{k-1}(p \omega_k^t+1)^n \sum_{i=0}^{k-2} \sum_{j=i+1}^{k-1} \omega_k^{-tj})
k1(np(p+1)n−1−k1∑t=0k−1(pωkt+1)n∑i=0k−2∑j=i+1k−1ωk−tj)
利用等比数列求和：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
t
=
0
k
−
1
(
p
ω
k
t
+
1
)
n
∑
i
=
0
k
−
2
ω
k
−
t
k
−
ω
k
−
t
(
i
+
1
)
ω
k
−
t
−
1
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k} \sum_{t=0}^{k-1} (p \omega_k^t+1)^n\sum_{i=0}^{k-2} \frac{\omega_k^{-tk}- \omega_{k}^{-t(i+1)}}{\omega_{k}^{-t}-1})
k1(np(p+1)n−1−k1∑t=0k−1(pωkt+1)n∑i=0k−2ωk−t−1ωk−tk−ωk−t(i+1))
整理式子，得到：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
t
=
0
k
−
1
(
p
ω
k
t
+
1
)
n
ω
k
−
t
−
1
∑
i
=
0
k
−
1
(
1
−
ω
k
−
t
(
i
+
1
)
)
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k}\sum_{t=0}^{k-1}\frac{(p \omega_k^t+1)^n}{\omega_{k}^{-t}-1}\sum_{i=0}^{k-1} (1- \omega_{k}^{-t(i+1)}))
k1(np(p+1)n−1−k1∑t=0k−1ωk−t−1(pωkt+1)n∑i=0k−1(1−ωk−t(i+1)))
根据单位根的性质：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
1
k
∑
t
=
0
k
−
1
(
p
ω
k
t
+
1
)
n
ω
k
−
t
−
1
k
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{1}{k}\sum_{t=0}^{k-1}\frac{(p \omega_k^t+1)^n}{\omega_{k}^{-t}-1}k)
k1(np(p+1)n−1−k1∑t=0k−1ωk−t−1(pωkt+1)nk)
最终得到：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
∑
i
=
0
k
−
1
(
p
ω
k
i
+
1
)
n
ω
k
−
i
−
1
)
\frac{1}{k}(np(p+1)^{n-1}-\sum_{i=0}^{k-1}\frac{(p \omega_k^i+1)^n}{\omega_{k}^{-i}-1})
k1(np(p+1)n−1−∑i=0k−1ωk−i−1(pωki+1)n)
这里的式子当
i
i
i 取
0
0
0时是错误的，中途不能使用等比数列求和公式。实际答案应该为：
1
k
(
n
p
(
p
+
1
)
n
−
1
−
k
−
1
2
(
p
+
1
)
n
−
∑
i
=
1
k
−
1
(
p
ω
k
i
+
1
)
n
ω
k
−
i
−
1
)
\frac{1}{k}(np(p+1)^{n-1}-\frac{k-1}{2}(p+1)^n-\sum_{i=1}^{k-1}\frac{(p \omega_k^i+1)^n}{\omega_{k}^{-i}-1})
k1(np(p+1)n−1−2k−1(p+1)n−∑i=1k−1ωk−i−1(pωki+1)n)
时间复杂度
O
(
k
log
2
n
)
O(k \log_2n)
O(klog2n)，空间复杂度
O
(
1
)
O(1)
O(1)
#include<iostream>
using namespace std;
#define R register int
#define L long long
#define I inline
#define P 998244353
I int PowMod(int x,int y){
int res=1;
while(y!=0){
if((y&1)==1){
res=(L)res*x%P;
}
y>>=1;
x=(L)x*x%P;
}
return res;
}
int main(){
int n,p,k,w,pw=1,ans=0;
cin>>n>>p>>k;
w=PowMod(3,(P-1)/k);
for(R i=1;i!=k;i++){
pw=(L)pw*w%P;
ans=((L)PowMod(((L)p*pw+1)%P,n)*PowMod(PowMod(pw,P-2)+P-1,P-2)+ans)%P;
}
ans=(499122177ll*(k-1)%P*PowMod(p+1,n)+ans)%P;
ans=((L)n*p%P*PowMod(p+1,n-1)-ans+P)%P;
cout<<(L)ans*PowMod(k,P-2)%P;
return 0;
}