题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2855
这题找规律比较难
代码：
#include<stdio.h>
int m;
__int64 a[2][2],b[2][2];
void Mul(__int64 c[2][2],__int64 d[2][2])
{
__int64 x[2][2],y[2][2];
x[0][0]=c[0][0];x[0][1]=c[0][1];
x[1][0]=c[1][0];x[1][1]=c[1][1];
y[0][0]=d[0][0];y[0][1]=d[0][1];
y[1][0]=d[1][0];y[1][1]=d[1][1];
c[0][0]=(x[0][0]*y[0][0]+x[0][1]*y[1][0])%m;
c[0][1]=(x[0][0]*y[0][1]+x[0][1]*y[1][1])%m;
c[1][0]=(x[1][0]*y[0][0]+x[1][1]*y[1][0])%m;
c[1][1]=(x[1][0]*y[0][1]+x[1][1]*y[1][1])%m;
}
void POW(int n)
{
if(n==1)
return;
POW(n/2);
Mul(a,a);
if(n%2==1)
Mul(a,b);
a[0][0]%=m;a[0][1]%=m;
a[1][0]%=m;a[1][1]%=m;
}
int main()
{
int ncase,n;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d%d",&n,&m);
if(n==0)
printf("0\n");
else if(n==1)
printf("%d\n",1%m);
else
{
a[0][0]=b[0][0]=3;a[0][1]=b[0][1]=1;
a[1][0]=b[1][0]=-1;a[1][1]=b[1][1]=0;
POW(n-1);
printf("%I64d\n",a[0][0]<0?a[0][0]+m:a[0][0]%m);
}
}
return 0;
}