题目分析：
这题的目标是求$$ \sum_{i \in [0,n),k \mid i} \binom{n}{i}G^i $$
这个形式很像单位根反演。
单位根反演一般用于求：$ \sum_{i \in [0,n),k \mid i} \binom{n}{i}f(x)^i $
推理过程略，实际上也就是交换求和符号的事情。
接着就变成裸的矩阵快速幂了
代码：
#include<bits/stdc++.h>
using namespace std; int m,k,p;long long n;
int l,s,t,gg; struct mat{int arr[][];}G,bs,mmp;
vector<int> fac; // factor of p void buildbase(int w){
for(int i=;i<=m;i++)
for(int j=;j<=m;j++) bs.arr[i][j] = 1ll*w*G.arr[i][j]%p;
for(int i=;i<=m;i++) bs.arr[i][i] ++,bs.arr[i][i] %= p;
} mat operator*(mat alpha,mat beta){
memset(mmp.arr,,sizeof(mmp.arr));
for(int k=;k<=m;k++){
for(int i=;i<=m;i++){
for(int j=;j<=m;j++){
mmp.arr[i][j] += 1ll*alpha.arr[i][k]*beta.arr[k][j]%p;
mmp.arr[i][j] %= p;
}
}
}
return mmp;
} mat res;
mat fstpow(mat now,long long pw){
memset(res.arr,,sizeof(res.arr));
for(int i=;i<=m;i++) res.arr[i][i] = ;
long long bit = ;
while(bit <= pw){
if(bit & pw){res = res*bs;}
bs = bs*bs;bit<<=;
}
return res;
} void init(){
memset(G.arr,,sizeof(G.arr));
fac.clear();
l = s = t = gg = ;
} void read(){
scanf("%d%d%d",&l,&s,&t);
for(int i=;i<=l;i++){
int u,v; scanf("%d%d",&u,&v);
G.arr[u][v]++;
}
} int fast_pow(int now,int pw){
int ans = ,dt = now,bit = ;
while(bit <= pw){
if(bit & pw){ans = 1ll*ans*dt%p;}
dt = 1ll*dt*dt%p; bit<<=;
}
return ans;
} void getgg(){
int z = p-;
for(int i=;i*i<=z;i++){
if(z % i == ){
fac.push_back(i);
while(z % i == ) z /= i;
}
}
if(z != ) fac.push_back(z);
for(int i=;i<=p;i++){
int flag = true;
for(int j=;j<fac.size();j++){
int z = fast_pow(i,(p-)/fac[j]);
if(z == ){flag = false; break;}
}
if(flag){gg = i;break;}
}
gg = fast_pow(gg,(p-)/k);
} void work(){
int w = ,ans = ;
for(int i=;i<k;i++,w = 1ll*w*gg%p){
buildbase(w);
bs = fstpow(bs,n);
ans += bs.arr[s][t]; ans%=p;
}
ans = 1ll*ans*fast_pow(k,p-)%p;
printf("%d\n",ans);
} int main(){
while(scanf("%d%lld%d%d",&m,&n,&k,&p) == ){
init();
read();
getgg();
work();
}
return ;
}