HDU 2276 Kiki & Little Kiki 2 （位运算+矩阵快速幂）

HDU 2276 Kiki Little Kiki 2 （位运算矩阵快速幂） ACM 题目地址：HDU 2276 Kiki Little Kiki 2 题意 ： 一排灯，开关状态已知，每过一秒：第i个灯会根据刚才左边的那个灯的开关情况变化，如果左边是开的，它就会变化，如果是关的，就保持原来状态。问m秒后

HDU 2276 Kiki & Little Kiki 2 （位运算+矩阵快速幂）

ACM

题目地址：HDU 2276 Kiki & Little Kiki 2

题意： 
一排灯，开关状态已知，每过一秒：第i个灯会根据刚才左边的那个灯的开关情况变化，如果左边是开的，它就会变化，如果是关的，就保持原来状态。问m秒后的状态。 
第1个的左边是最后一个。

分析： 
转移不好想啊。。。 
变化是这样的：

<ol>
<li><code><span>原来</span><span>左边</span><span>变化</span></code></li>
<li><code><span>1</span><span>1</span><span>0</span></code></li>
<li><code><span>1</span><span>0</span><span>1</span></code></li>
<li><code><span>0</span><span>1</span><span>1</span></code></li>
<li><code><span>0</span><span>0</span><span>0</span></code></li>
</ol>

然后想到 (~原来)^(左边)=变化 
发现搞不成矩阵TAT... 
看了别人题解后发现：(原来+左边)&2=变化，瞬间orz。 
不过这样想才没错，矩阵需要的是加法。

于是构造矩阵。见大神的矩阵：

<ol>
<li><code><span>"1 0 0...0 1</span></code></li>
<li><code><span> 1 1 0...0 0</span></code></li>
<li><code><span> 0 1 1...0 0</span></code></li>
<li><code><span> 0 0 1...0 0</span></code></li>
<li><code><span> ...........</span></code></li>
<li><code><span> 0 0 0...1 1</span></code></li>
<li><code><span>"</span></code></li>
</ol>

最后要注意，如果直接矩阵乘法%2会跪，因为数据太大了。 
这时候可以用位运算优化。 
我们注意到：(1+1)%2和1^1结果一样，1*1和1&1结果一样，所以相乘函数改下就行了。

代码：

/*
*  Author:      illuz <iilluzen>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2276.cpp
*  Create Date: 2014-08-03 22:47:12
*  Descripton:   
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define repf(i,a,b) for(int i=(a);i>= 1;
	}
	return c;
}

void init() {
	cin >> s;
	int len = s.length();
	a.n = b.n = c.n = len;
	a.init(0);
	b.init(0);
	c.init(0);

	repf (i, 0, len - 1) {
		b.v[i][0] = s[i] - '0';
	}
	a.v[0][0] = a.v[0][a.n - 1] = 1;
	repf (i, 1, a.n - 1) {
		a.v[i][i] = a.v[i][i - 1] = 1;
	}
}

void solve(int n) {
	c = a ^ (n);
	c = c * b;
	repf (i, 0, c.n - 1) {
		printf("%d", c.v[i][0]);
	}
	puts("");
}

int main() {
	while (~scanf("%d", &n)) {
		init();
		solve(n);
	}
	return 0;
}
</cmath></algorithm></iostream></cstring></cstdio></iilluzen>