描述

There are n lights in a circle numbered from 1 to n. The left of light 1 is light n, and the left of light k (1< k<= n) is the light k-1.At time of 0, some of them turn on, and others turn off.

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 !!! Given the initiation state, please find all lights’ state after M second. (2<= n <= 100, 1<= M<= 10^8)

输入

The input contains no more than 1000 data sets. The first line of each data set is an integer m indicate the time, the second line will be a string T, only contains ‘0’ and ‘1’ , and its length n will not exceed 100. It means all lights in the circle from 1 to n.

If the ith character of T is ‘1’, it means the light i is on, otherwise the light is off.

输出

For each data set, output all lights’ state at m seconds in one line. It only contains character ‘0’ and ‘1.

样例输入

1

0101111

10

100000001

样例输出

1111000

001000010

题意：给出一些灯的初始状态（用0、1表示）,

对这些灯进行m次变换;若当前灯的前一盏灯的状态为1,

则调整当前灯的状态,

0变为1,1变为0；否则不变。第1盏灯的前一盏灯是最后一盏灯。问最后每盏灯的状态。

分析：通过模拟可以发现,

假设有n盏灯,第i盏灯的状态为f[i],则f[i] = (f[i] + f[i-1])%2;

又因为这些灯形成了环,则f[i] = (f[i] + f[(n+i-2)%n+1])%2,

这样初始状态形成一个1*n的矩阵

根据系数推出初始矩阵,然后构造出如下n*n的矩阵:

1 1 0…… 0 0

0 1 1…… 0 0

………………………..

1 0 0…… 0 1

每次乘以这个矩阵得出的结果就是下一个状态。

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<vector>

#include<math.h>

#include<cstdio>

#include<sstream>

#include<numeric>//STL数值算法头文件

#include<stdlib.h>

#include <ctype.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<functional>//模板类头文件

using namespace std;

typedef long long ll;

const int maxn=1001;

const int INF=0x3f3f3f3f;

const int N = 102;

struct mat

{

    int r, c;

    int M[N][N];

    mat(int r, int c):r(r), c(c)

    {

        memset(M, 0, sizeof(M));

    }

};

mat mul(mat& A, mat& B)

{

    mat C(A.r, B.c);

    for(int i = 0; i < A.r; ++i)

        for(int j = 0; j < A.c; ++j)

            if(A.M[i][j])     //优化，只有state为1的时候才需要改变

            {

                for(int k = 0; k < B.r; ++k)

                    if(B.M[j][k])

                        C.M[i][k] ^= A.M[i][j] & B.M[j][k];

            }

    return C;

}

mat pow(mat& A, int k)

{

    mat B(A.r, A.c);

    for(int i = 0; i < A.r; ++i) B.M[i][i] = 1;

    while(k)

    {

        if(k & 1) B = mul(B, A);

        A = mul(A, A);

        k >>= 1;

    }

    return B;

}

int main()

{

    int m;

    char t[105];

    while(scanf("%d %s", &m, t) != EOF)

    {

        int n = strlen(t);

        mat A(1, n);

        mat T(n, n);

        for(int i = 0; i < n; ++i)

        {

            A.M[0][i] = t[i] - '0';

            T.M[i][i] = T.M[i][(i + 1) % n] = 1;

        }

        T = pow(T, m);

        A = mul(A, T);

        for(int i = 0; i < n; ++i)

        {

            printf("%d", A.M[0][i]);

        }

        printf("\n");

    }

    return 0;

}