Kiki & Little Kiki 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2032 Accepted Submission(s): 1046
Problem Description
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)
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)
Input
The input contains one or more 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.
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.
Output
For each data set, output all lights' state at m seconds in one line. It only contains character '0' and '1.
Sample Input
1 0101111 10 100000001
Sample Output
1111000 001000010
/*
HDU 2276 矩阵构造和乘法
题意：m表示m秒
下面一行表示n个灯（灯是排成环的，也就是说头尾相接）
灯亮暗由 1 0表示
对于任意一盏灯，当左边灯亮时，下一秒该灯将变换状态
问：输出m秒后灯的状态
a1 = (a1+an)%2,a2 = (a1+a2)%2,a3 = (a2+a3)%2,……an = (an+an-1)%2
然后就可以构造出矩阵了，根据上面的等式
初始表^n * 输入表
对于a0a1a2a3
|b0b1b2b3|= |1 0 0 1| ^m *|a0a1a2a3|
|1 1 0 0|
|0 1 1 0|
|0 0 1 1|
*/
#include<iostream>
#include<stdio.h>
using namespace std;
#define N 101
struct matrix{
int m[N][N];
};
matrix mat,ans;
char str[101];
int len;
void init()
{
int i;
memset(mat.m,0,sizeof(mat.m));
for(i=1;i<len;i++)
mat.m[i][i]=mat.m[i][i-1]=1;
mat.m[0][0]=mat.m[0][len-1]=1;//第一个字符与最后一个结合
}
matrix mul(matrix a,matrix b)
{
int i,j,k;
matrix c;
for(i=0;i<len;i++)
for(j=0;j<len;j++)
{
c.m[i][j]=0;
for(k=0;k<len;k++)
c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
}
return c;
}
void pow(matrix ma,int n)
{
int i;
memset(ans.m,0,sizeof(ans.m));
for(i=0;i<len;i++)
ans.m[i][i]=1;
for(;n;n>>=1)
{
if(n&1)
ans=mul(ans,ma);
ma=mul(ma,ma);
}
}
int main()
{
int n,x,i,j;
//freopen("test.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
scanf("%s",str);
len=strlen(str);
init();//建立初始的循环矩阵
pow(mat,n);//mat^n
for(i=0;i<len;i++)
{
x=0;
for(j=0;j<len;j++)
x^=ans.m[i][j]&(str[j]-'0');
printf("%d",x);
}
printf("\n");
}
return 0;
}