矩阵快速幂--模板

http://acm.bit.edu.cn/mod/programming/view.php?id=670

The Little Architect II

#include<stdio.h>
#include<string.h>

//dp方程：f[n]=3*f[n-1]+3*f[n-2]-f[n-3];
//矩阵快速幂  。。  模板
//构造矩阵
// 3 1 0
// 3 0 1
//-1 0 0
struct node
{
	long long a[3][3];
};

long long n,p;
node cheng(node A,node B)
{
	node C;
	memset(C.a,0,sizeof(C.a));
	int i,j,k;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++){
			for(k=0;k<3;k++)
				C.a[i][j]+=A.a[i][k]*B.a[k][j];
			C.a[i][j]%=p;
		}
	return C;
}

int main()
{
	int i,j,k;
	node I,T;
	
	while(~scanf("%lld%lld",&n,&p))
	{
		long long b[3]={2,9,32};
		for(i=0;i<3;i++)
			for(j=0;j<3;j++)
				if(i==j) I.a[i][j]=1;
				else I.a[i][j]=0;
		memset(T.a,0,sizeof(T.a));
		T.a[0][0]=3,T.a[1][0]=3,T.a[2][0]=-1;
		T.a[0][1]=1,T.a[1][2]=1;
		if(n<=3)
			printf("%lld\n",b[n-1]%p);
		else
		{
			n-=3;
			while(n>0)
			{
				if(n&1==1) I=cheng(I,T);
				n>>=1;
				T=cheng(T,T);
			}
			long long ans=(b[2]*I.a[0][0]+b[1]*I.a[1][0]+b[0]*I.a[2][0])%p;
			if(ans<0) ans+=p;
			printf("%lld\n",ans);
		}
	}
}