题意：一个中国环的游戏，规则是一个木棒上有n个环，第一个环是可以随意放上或拆下的，剩下的环x如果想放上或拆下必须前一个环x-1是放上的且前x-2个环全部是拆下的，问n个环最少多少次操作可以全部拆掉。
题解：需要进行递推，首先第一步肯定是要拆第n个环保证操作次数最少，因为后面的环是否存在对前面的环不造成影响，而先拆前面的如果要拆后面的环还是要把前面的放上，f(n)表示拆掉前n个环需要的最少操作次数，先拆第n个要拆前n-2个再拆第n个，花费f(n-2)+1，然后这时是00…0010，要拆第n-1个需要先把前n-2个放上，花费的步数和拆下是一样是f(n-2)，这时就是11…1110，全部拆掉就是f(n-1)，因此递推公式是f(n) = f(n-1) + 2 * f(n-2) + 1。最后矩阵快速幂就行了。

#include 
   
     #include 
    
      const int MOD = 200907; struct Mat { long long g[3][3]; }ori, res; long long n; Mat multiply(Mat x, Mat y) { Mat temp; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { temp.g[i][j] = 0; for (int k = 0; k < 3; k++) temp.g[i][j] = (temp.g[i][j] + x.g[i][k] * y.g[k][j]) % MOD; } return temp; } void calc(long long n) { while (n) { if (n & 1) ori = multiply(ori, res); n >>= 1; res = multiply(res, res); } } int main() { while (scanf("%lld", &n) == 1 && n) { if (n == 1 || n == 2) { printf("%lld\n", n); continue; } memset(ori.g, 0, sizeof(ori.g)); memset(res.g, 0, sizeof(res.g)); ori.g[0][0] = 2; ori.g[0][1] = ori.g[0][2] = 1; res.g[0][0] = res.g[0][1] = res.g[2][0] = res.g[2][2] = 1; res.g[1][0] = 2; calc(n - 2); printf("%lld\n", ori.g[0][0]); } return 0; }