单位根反演 小猪佩奇学数学

题面
一个比较纯粹的推式子题目，第一步先将整除拆开：
∑ 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−1​kj​∑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−1​j∑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−1​jω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)n​k)
最终得到：
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$ 取$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(klog2​n)，空间复杂度 $O(1)$

#include
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！