HDU (2276 Kiki & Little Kiki 2 )

spoiler posted @ 2011年4月28日 00:41 in 十个利用矩阵乘法解决的经典题目 , 2039 阅读

题目大意:题目大意给定一系列灯的初始状态,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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter