hdu 2276 Kiki & Little Kiki 2 矩阵快速幂

Change the state of light i (if it's on, turn off it; if it is not on, turn on it) at t+1 second (t >= 0), if the left of light i is on !!!

只有当第i个左边的灯是亮的（第0个的左边是最后一个，它是一个环），第i个就改变状态

d(t,i) = ( d(t-1,i) + d(t-1,i-1) )%2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int Mod = 2;
const int N = 105;
int msize;

struct Mat
{
    int mat[N][N];
};

Mat operator *(Mat a, Mat b)
{
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    for(int k = 0; k < msize; ++k)
        for(int i = 0; i < msize; ++i)
            if(a.mat[i][k])
                for(int j = 0; j < msize; ++j)
                    if(b.mat[k][j])
                        c.mat[i][j] = (a.mat[i][k] * b.mat[k][j] + c.mat[i][j])%Mod;
    return c;
}

Mat operator ^(Mat a, int k)
{
    Mat c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i = 0; i < msize; ++i)
        c.mat[i][i]=1;
    for(; k; k >>= 1)
    {
        if(k&1) c = c*a;
        a = a*a;
    }
    return c;
}

char s[N];

int main()
{
//    freopen("in.txt", "r", stdin);
    int m;
    while(scanf("%d", &m) == 1)
    {
        scanf("%s", s);
        msize = strlen(s);
        Mat A;
        memset(A.mat, 0, sizeof(A.mat));
        for(int i = 0; i < msize; i++)
            A.mat[i][i] = A.mat[i][(i + msize - 1) % msize] = 1;
        A = A^m;
        for(int i = 0; i < msize; i++)
        {
            int ans = 0;
            for(int j = 0; j < msize; j++)
                ans = (ans + A.mat[i][j]*(s[j]-'0'))%Mod;
            printf("%d", ans);
        }
        puts("");
    }
    return 0;
}