补档，之前做了忘记写blog了 题意（看不出来你就输了）：在nk个数中选择r(模k意义下)个的方案数%p 这不就是组合数= = 明显有f[i][j]=f[i-1][j]（不选i）+f[i-1][j-1]（选i） 当然你也可以理解为前i个选择了j个。（这不是废话嘛） 线性明显会炸，所以直接上矩阵快速幂，这个很明显了。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; typedef long long ll; struct matrix { ll mat[55][55]; }a,b,c,d; ll n,K,p,r; matrix operator *(matrix a,matrix b) { memset(d.mat,0,sizeof(d.mat)); fo(i,0,K-1) fo(j,0,K-1) fo(k,0,K-1) { d.mat[i][j]=(d.mat[i][j]+a.mat[i][k]*b.mat[k][j]%p)%p; } return d; } inline matrix pow(matrix a,ll b) { memset(c.mat,0,sizeof(c.mat)); fo(i,0,K-1)c.mat[i][i]=1; while (b) { if (b&1)c=c*a; a=a*a; b>>=1; } return c; } int main() { scanf("%lld%lld%lld%lld",&n,&p,&K,&r); a.mat[0][0]=b.mat[0][0]=1; b.mat[0][K-1]++; fo(i,1,K-1)b.mat[i][i]++,b.mat[i][i-1]++; b=pow(b,n*K); a=a*b; printf("%lld\n",a.mat[0][r]); return 0; }