HDU 2842 Chinese Rings （带常数矩阵+矩阵快速幂）

ACM

题目地址：HDU 2842 Chinese Rings

题意：
一种中国环，解开第k个环需要先解开前(k-2)个环，并留有第(k-1)环。问解开n环最少需要几步。

分析：
设f(n)表示解开n环。
1. 由于游戏规则，解开n环不能一下子把n-1全解开了，否则第n个就没法拿掉了。
2. 得先拿掉第n个：先完成f(n-2)，然后再拿掉第n环。
3. 然后放回前(n-2)，其实这也是f(n-2)，因为是一个逆的过程。
4. 最后就变成完成f(n-1)了。

那f(n-1)呢？那是它自己的事了。。。
所以f(n) = f(n-2)+1 + f(n-2) + f(n-1)。
第一次遇到含有常数的式子，常数原来可以用的啊。

  

   
| f[n] | | 1 2 1 | |f[n-2]|
   
|f[n-1]| = | 1 0 0 | * |f[n-1]|
   
| 1 | | 0 0 1 | | 1 |
  

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2842.cpp
*  Create Date: 2014-08-03 22:22:57
*  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 N = 31; const int SIZE = 3; // max size of the matrix const int MOD = 200907; struct Mat{ int n; ll 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("%lld ", 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]) % MOD; c.v[i][j] %= MOD; } } } 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; } ll solve(int n) { if (n <= 2) { return n; } // init a.v[0][1] = 2; a.v[0][0] = a.v[0][2] = a.v[1][0] = a.v[2][2] = 1; b.v[0][0] = 2; b.v[1][0] = b.v[2][0] = 1; c = a ^ (n - 2); c = c * b; return c.v[0][0]; } int main() { int n; while (~scanf("%d", &n) && n) { cout << solve(n) << endl; } return 0; }