题目大意：给定序列 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 ;
}