【HDU4990】递推式

题目大意：给定序列 1， 2， 5， 10， 21， 42， 85， 170， 341 …… 求第n项 模 m的结果

递推式 f[i]  = f[i - 2] + 2 ^ (i - 1);

方法一： 构造矩阵, 求递推式

方法二: 直接推公式，递推式求和，得到 f[n] = [2 ^ (n + 1) - 1] / 3 奇数， f[n] = [2 ^ (n + 1) - 2] / 3 偶数； 其实还可以进一步化简， 注意到 2 ^ 2k % 3 = 1, 2 ^ (2k + 1) % 3 = 2，于是 f[n] = 2 ^ (n + 1) / 3 ；于是答案就是 2 ^ (n + 1) % 3m / 3 (巧妙)

源码（矩阵）：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #define mem0(a) memset(a, 0, sizeof(a))

 #define LL __int64

 using namespace std;

 struct Node{

     LL a[][];

 };

 Node multi(Node a, Node b, int m)

 {

     Node ans;

     mem0(ans.a);

     for(int i = ; i < ; i++) {

         for(int j = ; j < ; j++) {

             for(int k = ; k < ; k++) {

                 ans.a[i][j] += (a.a[i][k] * b.a[k][j]) % m;

             }

         }

     }

     return ans;

 }

 Node calc(Node a, int b, int m)

 {

     if(b == ) return a;

     Node tmp = calc(a, b >> , m);

     int t = b & ;

     tmp = multi(tmp, tmp, m);

     if(t) tmp = multi(tmp, a, m);

     return tmp;

 }

 Node a0;

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int n, m;

     a0.a[][] = a0.a[][] = ;

     a0.a[][] = ;

     a0.a[][] = ;

     while(~scanf("%d%d", &n, &m)) {

         LL ans = ;

         if(n == ) {

             cout<<  % m<< endl;

             continue;

         }

         if(n == ) {

             cout<<  % m<< endl;

             continue;

         }

         if(n & ) {

             Node one = calc(a0, (n - ) >> , m);

             ans = (one.a[][] + one.a[][] * ) % m;

         }

         else {

             Node one = calc(a0, (n - ) >> , m);

             ans = (one.a[][] *  + one.a[][] * ) % m;

         }

         cout<< ans<< endl;

     }

     return ;

 }