【题解】[牛客OI周赛3-提高组]A.地斗主 矩阵快速幂

题目链接

#include<cstdio>
#include<cstring>
typedef long long ll;
int n,m,t,ans[5]={0,1,5,11,36};
struct Matrix{
	ll a[5][5];
};
Matrix operator *(Matrix a,Matrix b)
{
	Matrix c;memset(c.a,0,sizeof(c.a));
	for(int i=0;i<=3;i++)
	    for(int j=0;j<=3;j++)
	    {
	    	for(int k=0;k<=3;k++)
	    	    c.a[i][j]+=a.a[i][k]*b.a[k][j];
	    	c.a[i][j]%=m;
		}
	return c;
}
Matrix operator ^(Matrix a,int p)
{
	Matrix c;memset(c.a,0,sizeof(c.a));
	for(int i=0;i<=3;i++)c.a[i][i]=1;//单位矩阵
	while(p)
	{
		if(p&1)c=c*a;
		a=a*a;
		p>>=1;
	}
	return c;
}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		if(n<=4)printf("%d\n",ans[n]);
		else
		{
			Matrix a,b,c;memset(a.a,0,sizeof(a.a));memset(b.a,0,sizeof(b.a));
			a.a[0][0]=1;a.a[0][1]=5;a.a[0][2]=1;a.a[0][3]=-1;a.a[1][0]=1;a.a[2][1]=1;a.a[3][2]=1;
			b.a[0][0]=36;b.a[1][0]=11;b.a[2][0]=5;b.a[3][0]=1;
			c=a^(n-4);
			c=c*b;
			printf("%lld\n",(c.a[0][0]+m)%m);
		}
	}
	return 0;
}

总结

公式推导与矩阵快速幂好题