HDU 2276 Kiki & Little Kiki 2 （位運算+矩陣快速冪）

HDU 2276 Kiki & Little Kiki 2 （位運算+矩陣快速冪）

ACM

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

題意：
一排燈，開關狀態已知，每過一秒：第i個燈會根據剛才左邊的那個燈的開關情況變化，如果左邊是開的，它就會變化，如果是關的，就保持原來狀態。問m秒後的狀態。
第1個的左邊是最後一個。

分析：
轉移不好想啊。。。
變化是這樣的：

原來    左邊    變化
1       1       0
1       0       1
0       1       1
0       0       0

然後想到 (~原來)^(左邊)=變化
發現搞不成矩陣TAT...
看了別人題解後發現：(原來+左邊)&2=變化，瞬間orz。
不過這樣想才沒錯，矩陣需要的是加法。

於是構造矩陣。見大神的矩陣：

"1 0 0...0 1
 1 1 0...0 0
 0 1 1...0 0
 0 0 1...0 0
 ...........
 0 0 0...1 1
"

最後要注意，如果直接矩陣乘法%2會跪，因為數據太大了。
這時候可以用位運算優化。
我們注意到：(1+1)%2和1^1結果一樣，1*1和1&1結果一樣，所以相乘函數改下就行了。

代碼：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/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<=(b);i++)
typedef long long ll;

const int SIZE = 101;	// max size of the matrix

int n;
string s;

struct Mat{
	int n;
	int v[SIZE][SIZE];	// value of matrix

	Mat(int _n = SIZE) {
		n = _n;
		memset(v, 0, sizeof(v));
	}

	void init(ll _v) {
		memset(v, 0, sizeof(v));
		repf (i, 0, n - 1)
			v[i][i] = _v;
	}

	void output() {
		repf (i, 0, n - 1) {
			repf (j, 0, n - 1)
				printf("%d ", v[i][j]);
			puts("");
		}
		puts("");
	}
} a, b, c;

Mat operator * (Mat a, Mat b) {
	Mat c(a.n);
	repf (i, 0, a.n - 1) {
		repf (j, 0, a.n - 1) {
			c.v[i][j] = 0;
			repf (k, 0, a.n - 1) {
				c.v[i][j] ^= (a.v[i][k] & b.v[k][j]);
			}
		}
	}
	return c;
}

Mat operator ^ (Mat a, ll k) {
	Mat c(a.n);
	c.init(1);
	while (k) {
		if (k&1) c = c * a;
		a = a * a;
		k >>= 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;
}