题干：

Read the program below carefully then answer the question. 
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include <cstdio> 
#include<iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include<vector> 

const int MAX=100000*2; 
const int INF=1e9; 

int main() 
{ 
  int n,m,ans,i; 
  while(scanf("%d%d",&n,&m)!=EOF) 
  { 
    ans=0; 
    for(i=1;i<=n;i++) 
    { 
      if(i&1)ans=(ans*2+1)%m; 
      else ans=ans*2%m; 
    } 
    printf("%d\n",ans); 
  } 
  return 0; 
}

Input

Multi test cases，each line will contain two integers n and m. Process to end of file. 
[Technical Specification] 
1<=n, m <= 1000000000

Output

For each case，output an integer，represents the output of above program.

Sample Input

1 10
3 100

Sample Output

1
5

解题报告：

      根据题干找规律，发现f(n) = f(n-1) + 2 * f(n-2) +1

AC代码：

#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include <cstdio> 
#include<iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#define ll long long
struct Matrix {
	ll arr[4][4];
}unit,trans;
ll n,m,ans;  
Matrix mul( Matrix a,Matrix b,ll mod) {
	Matrix c;
	for(int i = 1; i<=3; i++) {
		for(int j = 1; j<=3; j++) {
			c.arr[i][j] = 0; 
			for(int k = 1; k<=3; k++) {
//				if(a.arr[i][k] && b.arr[k][j])
				c.arr[i][j] = (c.arr[i][j] + a.arr[i][k]*b.arr[k][j])%mod;
			}
		}
	}
	return c;
}
Matrix q_pow(Matrix a, ll k,ll mod) {
	Matrix ans;
	ans = unit;
	while(k) {
		if(k&1) {
			ans=mul(ans,a,m);
		}
		k>>=1;
		a=mul(a,a,m);
	}
	return ans;
}
void init() {
	memset(unit.arr,0,sizeof(unit.arr) );
	for(int i = 1; i<=3; i++) {
		unit.arr[i][i] = 1;
		trans.arr[i][1] = trans.arr[i][2] = trans.arr[i][3] = 0;
	}
	trans.arr[1][1]=trans.arr[1][3] =trans.arr[2][1]=trans.arr[3][3] = 1;
	trans.arr[1][2] = 2;
}
int main() 
{ 
	Matrix ans;
  	ll sum=0;
	while(scanf("%lld%lld",&n,&m)!=EOF) {
  		sum = 0;
		init();
		if(n==1) {
			printf("%lld\n",1%m);
			continue;	
		}
		else if(n == 2) {
			printf("%lld\n",2%m);continue;
		}
  		ans = q_pow(trans,n-2,m);
  		sum = ans.arr[1][1]*2 + ans.arr[1][2]*1 + ans.arr[1][3];
  		printf("%lld\n",sum%m);
	  }
	return 0; 
}

总结：

      这题坑很多啊，总是巧妙的跳了进去。

      1.全局变量ll的n和m，结果输入用%d这个题的Mul函数 不是i<=n了！而是i<=3即可，i<=n就错了！  此题和HDU - 5015不一样，不是矩阵是个不确定的矩阵！所以这里是小于等于3！！即

      2.输出的时候n=1和n=2需要特判一下，因为你传参是n-2。即：这种地方一定要小心！你的函数是有使用条件的，这一点不仅适用于矩阵快速幂，还有很多其他的地方。

     3.输出n==2的时候，别忘了也需要取模！！

    4.最后的输出 也需要取模！