- 描写叙述
- 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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
char state[N];
struct Matrix {
Matrix() {}
void Init(int n) {
row = n; col = n;
memset(mat, 0, sizeof(mat));
for(int i = 0; i < n; i++)
mat[i][i] = 1;
}
void Init(int m, int n) {
row = m; col = n;
memset(mat, 0, sizeof(mat));
}
int row, col;
int mat[N][N];
const Matrix &Pow(int n);
}; const Matrix &operator *(const Matrix &A, const Matrix &B) {
Matrix res;
res.Init(A.row, B.col);
for(int i = 0; i < A.row; i++) {
for(int j = 0; j < A.col; j++) {
if(A.mat[i][j]) {
for(int k = 0; k < B.col; k++) {
if(B.mat[j][k])
res.mat[i][k] = res.mat[i][k] ^ (A.mat[i][j] & B.mat[j][k]);
}
} }
}
return res;
} const Matrix &Matrix::Pow(int n) {
Matrix tmp, pre;
tmp = *this;
pre.Init(this->row);
while(n) {
if(n&1) pre = tmp * pre;
tmp = tmp * tmp;
n >>= 1;
}
return pre;
} int main() {
int m;
Matrix A, B, ans;
while(~scanf("%d", &m)) {
scanf("%s",state);
int len = strlen(state);
A.Init(1, len);
for(int i = 0; i < len; i++)
A.mat[0][i] = state[i] - '0';
B.Init(len);
for(int i = 0; i < len; i++) {
B.mat[i][i] = 1;
B.mat[i][(i+1)%len] = 1;
}
ans = A * B.Pow(m);
for(int i = 0; i < len; i++)
printf("%d", ans.mat[0][i]);
printf("\n");
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。