题目大意:
给出一段只含序列'0'和'1'的序列,形成一个圆环,以及时间M,每结果1单位时间,如果a[i-1]==1(当i==0时,i-1为n-1),则a[i]^=1;
求M时间后的序列
中间有一段写错了,搜了博客才知道原来是对2取模,我理解成不是1就是0
AC代码:
#include<iostream> #include<cstring> using namespace std; #define ll long long const int maxn=105; const int mod=10000; int T,n; struct matrix{ int a[maxn][maxn]; matrix(){ memset(a,0,sizeof(a)); } }; matrix mul(matrix a,matrix b){ matrix res; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ for(int k=0;k<n;k++) res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]); res.a[i][j]%=2;//淦,搜了博客才知道这里错了,居然是%2,还以为除了1以外全是0; } return res; } matrix qpow(matrix A,ll m){//方阵A的m次幂 matrix ans; /*for(int i=0;i<n;i++){ for(int j=0;j<n;j++) cout<<A.a[i][j]<<' '; cout<<endl; }*/ for(int i=0;i<n;i++) ans.a[i][i]=1; //单位矩阵 while(m){ if(m&1)ans=mul(ans,A); A=mul(A,A); m>>=1; } return ans; } int main(){ while(cin>>T){ char s[105]; cin>>s; n = strlen(s); matrix m,cnt; for(int i=0;i<n;i++){ m.a[0][i]=s[i]-'0'; } for(int i=0;i<n;i++){ cnt.a[i][i]=1;cnt.a[(i-1)>=0?(i-1):(n-1)][i]=1; } matrix res = mul(m,qpow(cnt,T)); for(int i=0;i<n;i++) cout<<res.a[0][i]; cout<<endl; } }