1 #include <stdio.h> 2 #include <string.h> 3 #define ll long long 4 const int maxn = 505; 5 ll n,m,d,k,a[maxn]; 6 struct mat{ // 结构体循环矩阵，原矩阵式方阵 7     ll v[maxn]; 8     mat() {memset(v,0,sizeof(v));} // 构造函数 9     mat operator*(mat c){ // 重载乘法运算符10         mat ans;11         // 只需计算出循环矩阵的第一行即可12         for(int i = 0 ; i < n ; i++)13         for(int j = 0 ; j < n ; j++)14             ans.v[i] = ((ans.v[i] + v[j] * c.v[(i - j + n) % n]) % m + m) % m;15           return ans;16      }17 };18 // 此处不用担心溢出，况且考虑到不好写单位矩阵，就用的方式啦19 mat pow_mod(mat x,ll k){20     mat y; y.v[0] = 1;21     while(k){22         if(k & 1) y = y * x;23         x = x * x;24         k >>= 1;25     }26     return y;27     // 递归写法28     //if(k == 1) return x;29     //mat sb = x * x;30     //mat ans = pow_mod(sb,k >> 1);31     //if(k & 1) ans = ans * x;32     //return ans;33 }