描述
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;
}