BZOJ 4870: [Shoi2017]组合数问题 矩阵乘法_递推

#include <cstdio>
#include <cstring>
#include <algorithm> 

#define setIO(s) freopen(s".in","r",stdin)
#define N 60
#define ll long long  
#define mod p

using namespace std;

int k,r;
long long n,p; 
struct matrix{
    long long mat[N][N];
}; 
void init(matrix &a){
    for(int i=0;i<k;++i)
        for(int j=0;j<k;++j) a.mat[i][j]=0;
}
void get(matrix &a){
    init(a);
    for(int i=0;i<k;++i) a.mat[i][i]=1; 
}
matrix operator*(matrix a,matrix b){
    matrix c;
    init(c);
    for(int i=0;i<k;++i)
        for(int j=0;j<k;++j)
            for(int kk=0;kk<=k;++kk) 
                c.mat[i][j]=(c.mat[i][j]+(long long)(a.mat[i][kk]*b.mat[kk][j]))%mod;
    return c;
}
matrix operator^(matrix a,ll p){
    matrix res;
    get(res);
    while(p>0){
        if(p&1) res=res*a;
        a=a*a;
        p>>=1;
    }
    return res;
}
int main(){
    //setIO("input"); 
    scanf("%lld%lld%d%d",&n,&mod,&k,&r);
    matrix ans,a; 
    init(ans),init(a),ans.mat[0][0]=1;
    for (int i=0;i<k;i++)
        a.mat[i?i-1:k-1][i]++,a.mat[i][i]++; 
    n*=k;
    ans=ans*(a^n);
    printf("%lld\n",ans.mat[0][r]);
    return 0; 
}