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; }