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 *  Blog:        http://blog.gaodaima.com/hcbbt*  File:        2276.cpp*  Create Date: 2014-08-03 22:47:12*  Descripton:   */#include #include #include #include #include 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] - '<p>本文来源gao!daima.com搞$代!码#网#</p>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;}

喜欢 (0)赏

[搞代码]

分享 (0)