题目分析:[y1,y2,,,,,yn]=ma[][]*[x1,x2,,,,xn],
ma[1][n]=1; ma[i-1][i]=1(2<=i<=n);
注意:矩阵结果相乘后记得mod2;
代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<memory.h> using namespace std; struct node { int matrix[101][101]; }ma,e; int n; node operator * (node x,node y) { node temp; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { temp.matrix[i][j]=0; for(int k=1;k<=n;k++) temp.matrix[i][j]+=(x.matrix[i][k]*y.matrix[k][j]); temp.matrix[i][j]%=2; } return temp; } node operator ^(node x,int k) { node ans=e,p=x; while(k) { if(k&1) { ans=ans*p; } k=k/2; p=p*p; } return ans; } int main() { int m; while(scanf("%d",&m)!=EOF) { memset(ma.matrix,0,sizeof(ma.matrix)); memset(e.matrix,0,sizeof(e)); char s[102]; scanf("%s",&s); n=strlen(s); for(int i=1;i<=n;i++) { if(i==1) ma.matrix[i][1]=ma.matrix[i][n]=1; else ma.matrix[i][i-1]=ma.matrix[i][i]=1; e.matrix[i][i]=1; } node t=ma^m; int ans[101],temp[101]; memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) if(s[i-1]=='1') temp[i]=1; else temp[i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) ans[i]+=(t.matrix[i][j]*temp[j]); ans[i]%=2; } for(int i=1;i<=n;i++) printf("%d",ans[i]); printf("\n"); } return 0; }