51nod 1122 机器人走方格 V4 【矩阵快速幂】

首先建立矩阵，给每个格子编号，然后在4*4的格子中把能一步走到的格子置为1，然后乘n次即可，这里要用到矩阵快速幂

#include<iostream>

#include<cstdio>

using namespace std;

const int mod=1e9+7;

long long n,ans;

struct qwe

{

	long long a[5][5];

	qwe operator * (qwe b)

	{

		qwe c;

		for(long long i=1;i<=4;i++)

			for(long long j=1;j<=4;j++)

				c.a[i][j]=0;

		for(long long k=1;k<=4;k++)

			for(long long i=1;i<=4;i++)

				for(long long j=1;j<=4;j++)

					c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%mod;

		return c;

	}

}a,r;

int main()

{

	scanf("%lld",&n);

	for(long long i=1;i<=4;i++)

		for(long long j=1;j<=4;j++)

			a.a[i][j]=1;

	a.a[1][4]=0,a.a[2][3]=0,a.a[3][2]=0,a.a[4][1]=0;

	for(long long i=1;i<=4;i++)

		r.a[i][i]=1;

	while(n)

	{

		if(n&1)

			r=r*a;

		a=a*a;

		n>>=1;

	}

	for(long long i1=1;i1<=4;i1++)

		for(long long i2=1;i2<=4;i2++)

			if(i2!=i1)

				for(long long i3=1;i3<=4;i3++)

					if(i3!=i1&&i3!=i2)

						for(long long i4=1;i4<=4;i4++)

							if(i4!=i1&&i4!=i2&&i4!=i3)

								ans=(ans+r.a[1][i1]*r.a[2][i2]%mod*r.a[3][i3]%mod*r.a[4][i4]%mod)%mod;

	printf("%lld\n",ans);

	return 0;

}