学步园

参考这里http://hi.baidu.com/nanjingtianzi/item/2ad2e23d77e746667c034b63

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;
struct node 
{
	int matrix[3][3];
}ma,e;
int m,n;
node operator *(node x,node y)
{
	node temp;
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
		{
			temp.matrix[i][j]=0;
			for(int k=1;k<=2;k++)
				temp.matrix[i][j]+=x.matrix[i][k]*y.matrix[k][j];
			temp.matrix[i][j]%=m;
		}
	return temp;
}
node operator ^(node x,int k)
{
	node ans=e,p=x;
	while(k)
	{
		if(k&1)
		{
			ans=ans*p;
		}
		k=k/2;
        p=p*p;
	}
	return ans;
}
int main()
{
	int T;
	scanf("%d",&T);
	memset(e.matrix,0,sizeof(e.matrix));
	memset(ma.matrix,0,sizeof(ma.matrix));
	e.matrix[1][1]=e.matrix[2][2]=ma.matrix[1][1]=ma.matrix[1][2]=ma.matrix[2][1]=1;
	while(T--)
	{
		scanf("%d %d",&n,&m);
		int ans;
		if(n==0)
			 ans=0;
		else
		{
		    node temp=(ma^(2*n-1));
			/*for(int i=1;i<=2;i++)
			{
				for(int j=1;j<=2;j++)
					printf("%d  ",temp.matrix[i][j]);
				printf("\n");
			}*/
			ans=temp.matrix[1][1]%m;;
		}
		printf("%d\n",ans);
	}
	system("pause");
	return 0;
}