两种构造的方式都是正确的；
1.
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 60 #define ll long long using namespace std; int x; ll M,n; struct matrix { int len_x; int len_y; ll data[maxn][maxn]; void ini() { len_x=0; len_y=0; memset(data,0,sizeof data); } }; matrix mat_big; ll f[maxn][maxn]; matrix s; matrix mat_mul(matrix mat,matrix t) { matrix ans; ans.ini(); ans.len_x=mat.len_x; ans.len_y=t.len_y; for(int i=0; i<mat.len_x; i++) { for(int j=0; j<t.len_y; j++) { for(int k=0; k<mat.len_y; k++) { ans.data[i][j]+=(mat.data[i][k]*t.data[k][j])%M; ans.data[i][j]%=M; } } } return ans; } int main() { f[0][0]=1; for(int i=1; i<maxn; i++) for(int j=0; j<=i; j++) { f[i][j]=f[i-1][j]+f[i-1][j-1]; } while(scanf("%lld%d%lld",&n,&x,&M)&&n!=-1) { mat_big.ini(); mat_big.len_x=x+2; mat_big.len_y=x+2; for(int i=0; i<=x; i++) for(int j=0; j<=i; j++) { mat_big.data[i][j]=x*f[i][j]; if(mat_big.data[i][j]>M)mat_big.data[i][j]%=M; } // for(int i=0; i<=x; i++) // mat_big.data[x+1][i]=mat_big.data[x][i]; mat_big.data[x+1][x+1]=1; mat_big.data[x+1][x]=1; s.ini(); s.len_y=1; s.len_x=x+2; s.data[0][0]=1; s.data[x+1][0]=0; // for(int i=0;i<=x+1;i++) // s.data[i][0]=1; matrix ret; ret.ini(); ret.len_x=x+2; ret.len_y=x+2; for(int i=0; i<ret.len_x; i++) ret.data[i][i]=1; n++; while(n) { if(n&1)ret=mat_mul(ret,mat_big); n>>=1; mat_big=mat_mul(mat_big,mat_big); } matrix ans=mat_mul(ret,s); printf("%lld ",ans.data[x+1][0]); } return 0; }
2.
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 60 #define ll long long using namespace std; int x; ll M,n; struct matrix { int len_x; int len_y; ll data[maxn][maxn]; void ini() { len_x=0; len_y=0; memset(data,0,sizeof data); } }; matrix mat_big; ll f[maxn][maxn]; matrix s; matrix mat_mul(matrix mat,matrix t) { matrix ans; ans.ini(); ans.len_x=mat.len_x; ans.len_y=t.len_y; for(int i=0; i<mat.len_x; i++) { for(int j=0; j<t.len_y; j++) { for(int k=0; k<mat.len_y; k++) { ans.data[i][j]+=(mat.data[i][k]*t.data[k][j])%M; ans.data[i][j]%=M; } } } return ans; } int main() { f[0][0]=1; for(int i=1; i<maxn; i++) for(int j=0; j<=i; j++) { f[i][j]=f[i-1][j]+f[i-1][j-1]; } while(scanf("%lld%d%lld",&n,&x,&M)&&n!=-1) { mat_big.ini(); mat_big.len_x=x+2; mat_big.len_y=x+2; for(int i=0; i<=x; i++) for(int j=0; j<=i; j++) { mat_big.data[i][j]=x*f[i][j]; if(mat_big.data[i][j]>M)mat_big.data[i][j]%=M; } for(int i=0; i<=x; i++) mat_big.data[x+1][i]=mat_big.data[x][i]; mat_big.data[x+1][x+1]=1; // mat_big.data[x+1][x]=1; s.ini(); s.len_y=1; s.len_x=x+2; s.data[0][0]=1; s.data[x+1][0]=0; // for(int i=0;i<=x+1;i++) // s.data[i][0]=1; matrix ret; ret.ini(); ret.len_x=x+2; ret.len_y=x+2; for(int i=0; i<ret.len_x; i++) ret.data[i][i]=1; while(n) { if(n&1)ret=mat_mul(ret,mat_big); n>>=1; mat_big=mat_mul(mat_big,mat_big); } matrix ans=mat_mul(ret,s); printf("%lld ",ans.data[x+1][0]); } return 0; }