题目分析：
构造f[nk][r]表示题目中要求的东西。容易发现递推公式f[nk][r]=f[nk-1][r]+f[nk-1][(r-1)%k].矩阵快速幂可以优化，时间复杂度O(k^3logn)。
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,p,k,r; 5 6 long long mat[56][56]; 7 long long g[56][56]; 8 long long t[56][56]; 9 10 void fast_pow(long long pw){ 11 if(pw == 1) { 12 for(int i=0;i<k;i++) for(int j=0;j<k;j++) g[i][j] = mat[i][j]; 13 return; 14 } 15 fast_pow(pw/2); 16 for(int i=0;i<k;i++) for(int j=0;j<k;j++) t[i][j] = g[i][j]; 17 memset(g,0,sizeof(g)); 18 for(int o=0;o<k;o++){ 19 for(int i=0;i<k;i++){ 20 for(int j=0;j<k;j++){ 21 g[i][j] += (t[i][o]*t[o][j])%p; 22 g[i][j] %= p; 23 } 24 } 25 } 26 if(pw&1){ 27 for(int i=0;i<k;i++) for(int j=0;j<k;j++) t[i][j] = g[i][j]; 28 memset(g,0,sizeof(g)); 29 for(int o=0;o<k;o++){ 30 for(int i=0;i<k;i++){ 31 for(int j=0;j<k;j++){ 32 g[i][j] += (t[i][o]*mat[o][j])%p; 33 g[i][j] %= p; 34 } 35 } 36 } 37 } 38 } 39 40 void BuildMat(){ 41 for(int i=0;i<k;i++){ 42 mat[i][i] += 1; mat[i][(i-1+k)%k] += 1; 43 } 44 } 45 46 void work(){ 47 BuildMat(); 48 fast_pow(1ll*n*k); 49 printf("%lld",g[r][0]); 50 } 51 52 int main(){ 53 scanf("%d%d%d%d",&n,&p,&k,&r); 54 work(); 55 return 0; 56 }