HDU (2276 Kiki & Little Kiki 2 )

题目大意：题目大意给定一系列灯的初始状态，0代表暗，1代表亮，每一秒所有的灯都有可能发生状态切换，

切换规则：当前灯的左边第一个灯是亮的，则当前的灯切换状态，如果当前灯的左边第一盏灯是暗的，则当前灯的状态无需变化！

注意：最左边的参考左右边那栈灯。

题目分析;

首先有两种情况：

左边第一盏灯亮的：

                              当前灯的动作:     1->0;    0->1;

左边第一盏灯暗的：

                               当前灯的动作：

                                                    1->1;      0->0;

我们可以看到的是， 可以用一个方程来模拟这个过程： F[i] = ( f [ i] +f [i+n-2]%n+1 )%2;

所以我们只要计算这个值就OK啦。

然后由于数据过大，开数组肯定会爆掉～

这里我们要想到的是 矩阵是一个模拟递归的高效算法

这里我们要构造一个 可以计算如上的方程的矩阵：

              1 0 0...0 1

              1 1 0...0 0

             0 1 1..0 0

             0 0 1..0 0

            . . . 0 ....

           . . .0.....

           0 0 0..0 1

然后再把f[n]...到f[1]构成一个矩阵和他相乘，正好就是达到了表达式的效果。如果还有不懂的那请您留言，我这里画图不方便悲剧的很

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char sim[102];
struct M{
	int s[101][101];
};
struct M unit,res,tempt;
int n,t;
struct M multiply(struct M a,struct M b){
	struct M c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			c.s[i][j]=0;
			for(int k=1;k<=n;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%2)%2;
		}
	return c;
}
void paw(){
	struct M ans=unit;
	struct M a=tempt;
	while(t){
		if(t%2==1)
			ans=multiply(ans,a);					
		a=multiply(a,a);
		t/=2;
	}
	res=multiply(res,ans);
}
int main(){
	int i,j,k;
	memset(unit.s,0,sizeof(unit.s));
	for(i=1;i<=100;i++)
			unit.s[i][i]=1;
	while(scanf("%d %s",&t,sim)!=EOF){
		memset(tempt.s,0,sizeof(tempt.s));
		memset(res.s,0,sizeof(res.s));
		k=strlen(sim);
		n=k;
		for(i=1;i<=k;i++)
			res.s[1][i]=sim[k-i]-'0';
		for(i=1;i<=n;i++){
			if(i!=n)
				tempt.s[i][i]=tempt.s[i+1][i]=1;
			else
				tempt.s[1][n]=tempt.s[n][n]=1;
		}
		paw();
		for(int i=n;i>=1;i--)
			printf("%d",res.s[1][i]);
		printf("\n");
	}
	return 0;
}