1 #include<cstdio> 2 #include<cstring> 3 const int maxn = 100; 4 typedef struct{ 5    long long Mat[maxn][maxn]; 6 }MAT; 7 long long MOD,d; // d是方阵的行数或者列数 8 // 方阵的乘法，模MOD 9 MAT mul(MAT a,MAT b){10    MAT c;11    memset(c.Mat,0,sizeof(c.Mat));12    for(int i = 1 ; i <= d ; i++)13    for(int j = 1 ; j <= d ; j++)14    for(int k = 1 ; k <= d ; k++)15    c.Mat[i][j] = (c.Mat[i][j] + a.Mat[i][k] * b.Mat[k][j]) % MOD;16    return c;17 }18 // 方阵快速幂19 MAT Quick_pow(MAT a,long long b){20    MAT c; memset(c.Mat,0,sizeof(c.Mat));21    for(int i = 1 ; i <= d ; i++) c.Mat[i][i] = 1;22    while(b){23       if(b & 1) c = mul(c,a);24       a = mul(a,a);25       b >>= 1;26    }27    return c;28 }