HDU2276 Kiki & Little Kiki 2

题目大意:

　　给出一段只含序列'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;
    }
}