单位根反演
\[[n|a]=\dfrac{1}{n}\sum\limits_{k=0}^{n-1}w^{ak}_{n} \]证明：
当\(i\not\equiv 0\pmod n\)时，由等比数列求和公式可得：
原式\(=\dfrac{1}{n}\times \dfrac{w^{an}_n-1}{w^a_{n}-1}\)，而右边分子为0，分母不为0，因此和为0。
当\(i\equiv 0\pmod n\)时，有原式\(=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}w^0_n=1\)。
qoj5370
求\(\sum\limits_{j=0}^{\infty}\binom{k}{i+jn}\)。
推式子：
\[\begin{aligned} \sum\limits_{j=0}^{\infty}\binom{k}{i+jn}&=\sum\limits_{v=0}^k\binom{k}{v}\dfrac{\sum_{j=0}^{n-1}(w^{v-i}_n)^j}{n}\\ &=\dfrac{1}{n}\sum\limits_{j=0}^{n-1}w^{-ij}_n\sum\limits_{v=0}^k\binom{k}{v}w^{vj}_n\\ &=\dfrac{1}{n}\sum\limits_{j=0}^{n-1}w^{-ij}_n(1+w^j_n)^k \end{aligned}\]求出单位根就可以直接求了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,k,p,mod,P;
int st[105],hst;
inline int qpow(int x,int k){x%=mod;int ans=1;for(;k;k>>=1,x=1ll*x*x%mod)if(k&1)ans=1ll*ans*x%mod;return ans;}
inline bool check(int x){
for(int i=1;i<=hst;i++){
if(qpow(x,P/st[i])==1)return 0;
}
return 1;
}
inline int getw(){
int s=sqrt(mod),x=mod-1;
hst=0;
for(int i=2;i<=s;i++)if(x%i==0){
st[++hst]=i;
while(x%i==0)x/=i;
}
if(x>1)st[++hst]=x;
for(int i=2;i<=mod;i++)if(check(i)){
return i;
break;
}
return 0;
}
inline void solve(){
cin>>n>>p>>k>>m>>mod;
m=((p-m)%n+n)%n;
P=mod-1;
int w=getw();
// cout<<w<<" ";
w=qpow(w,P/n);
// cout<<w<<endl;
int inv=qpow(w,P-m),ans=0;
for(int i=0,x=1,y=1;i<n;i++){
ans=(ans+1ll*y*qpow(1+x,k)%mod)%mod;
y=1ll*y*inv%mod,x=1ll*x*w%mod;
}
ans=1ll*ans*qpow(n,mod-2)%mod;
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}