学步园

一看到开关灯问题，觉得应该是和矩阵有关系的，于是开始向矩阵上靠，发现第i个灯的下一次变化为 （i-1 + i）&1; 这样就可以构造矩阵了，很高兴没有trick

code：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 101;

int n,m;
char str[MAXN];
bool dat[MAXN];
bool ans[MAXN];
struct Matrix
{
    bool mat[MAXN][MAXN];
}E,A;

void init()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            E.mat[i][j] = (i==j);
            A.mat[i][j] = 0;
        }
    }
    A.mat[1][1]=1;
    A.mat[1][n]=1;
    for(i=2;i<=n;i++)
    {
        A.mat[i][i-1]=1;
        A.mat[i][i]=1;
    }
}

Matrix operator * (const Matrix a,const Matrix b)
{
    Matrix res;
    int i,j,k;
    for(i=1;i<=n;i++)
    {

        for(j=1;j<=n;j++)
        {
            res.mat[i][j]=0;
            for(k=1;k<=n;k++)
            {
                res.mat[i][j]= (res.mat[i][j] + a.mat[i][k] * b.mat[k][j]) &1;
            }
        }
    }
    return res;
}

Matrix operator ^ (const Matrix a,int exp)
{
    Matrix res=E;
    Matrix tmp=a;
    while(exp)
    {
        if(exp&1)
            res = res * tmp;
        exp>>=1;
        tmp = tmp * tmp;
    }
    return res;
}

void solve()
{
    Matrix tmp = A ^ m;
    int i,j;
    for(i=1;i<=n;i++)
    {
        ans[i]=0;
        for(j=1;j<=n;j++)
        {
            ans[i]=(ans[i] + dat[j] * tmp.mat[i][j])&1;
        }
    }
    for(i=1;i<=n;i++)
    {
        printf("%d",ans[i]);
    }
    puts("");
}

int main()
{
    int i;
    while(~scanf("%d",&m))
    {
        scanf("%s",str);
        n=strlen(str);
        init();
        for(i=0;i<n;i++)
        {
            dat[i+1] = str[i]-'0';
        }
        solve();
    }
	return 0;
}