首页 > 代码库 > HDU 2276 Kiki & Little Kiki 2 （位运算+矩阵快速幂）

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

2024-07-15 15:01:05   222人阅读

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

ACM

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

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

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

  1. 原来    左边    变化
  2. 1       1       0
  3. 1       0       1
  4. 0       1       1
  5. 0       0       0

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

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

  1. "1 0 0...0 1
  2.  1 1 0...0 0
  3.  0 1 1...0 0
  4.  0 0 1...0 0
  5.  ...........
  6.  0 0 0...1 1
  7. "

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

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  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<=(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;
}



联系
我们