五校联考R1 Day1T3 平面图planar(递推 矩阵快速幂)

时间：2022-10-27 23:32:55

题目链接

我们可以把棱柱拆成有\(n\)条高的矩形，尝试递推。

在计算的过程中，第\(i\)列(\(i\neq n\))只与\(i-1\)列有关，称\(i-1\)列的上面/下面为左上/左下，第\(i\)列的上面/下面为右上/右下。

我们可以发现，右上可选的颜色数与左上和右下是否同色有关，右下同理，那就记\(f[i][0/1][0/1]\)表示左上与右下是否同色，左下与右上是否同色。

但是第\(n\)列和第\(1\)列不能同色，最后怎么算答案？

不知道第\(n\)列状态算不了，所以我们还要记第\(i\)列的上/下是否与第\(1\)列的上&下同色。称\(1\)列的上面/下面为左上/左下，我们发现这样只记与第\(1\)列的情况就可以知道第\(i-1\)列怎么转移到第i列了(这谁发现了。。)。

那么 \(f[i][0/1/2][0/1/2]\) 表示到第\(i\)列，右上的颜色 与左上、左下都不相同/与左上相同/与左下相同；右下的颜色 与左上、左下都不相同/与左上相同/与左下相同 的方案数。

最后的答案就是\(\sum f[n][j\neq 1][k\neq 2]\)(就是\(f[n+1][1][2]\))。可以递推啦。

改成矩阵快速幂就可以AC了。这个矩阵还算好推。

有两组状态是对称的，可以把状态压成5*5？不过没什么用。

转移好恶心啊。

65分递推：

#include <cstdio>

#include <algorithm>

#define mod (1000000007)

typedef long long LL;

const int N=1e6+5;

LL n,m,f[N][3][3];

inline LL FP(LL x,LL k)

{

	LL t=1; //x%=mod;

	for(; k; k>>=1,x=x*x%mod)

		if(k&1) t=t*x%mod;

	return t;

}

int main()

{

	freopen("planar.in","r",stdin);

	freopen("planar.out","w",stdout);

	scanf("%lld%lld",&n,&m);

	if(m==2) return putchar(n&1?'0':'2'),0;

	f[1][1][2]=m*(m-1)%mod;

	LL m3=(m-3)*(m-3)%mod, m2=(m-2)*(m-2)%mod, m23=(m-2)*(m-3)%mod, m34=(m3-m+4+mod)%mod;

	for(int i=2; i<=n; ++i)

	{//LONG_LONG_MAX=9e18 > 4e9*1e9

//		LL (*pre)[3]=f[i-1];//慢了smg

		f[i][0][0]=(f[i-1][0][0]*m34%mod+

					(f[i-1][0][1]+f[i-1][0][2]+f[i-1][1][0]+f[i-1][2][0])*m3%mod+

					(f[i-1][1][2]+f[i-1][2][1])*m23%mod)%mod;

		f[i][0][1]=((f[i-1][0][0]+f[i-1][0][2])*(m-3)%mod+

					(f[i-1][1][0]+f[i-1][2][0]+f[i-1][1][2])*(m-2)%mod)%mod;

		f[i][1][0]=((f[i-1][0][0]+f[i-1][2][0])*(m-3)%mod+

					(f[i-1][0][1]+f[i-1][0][2]+f[i-1][2][1])*(m-2)%mod)%mod;

		f[i][0][2]=((f[i-1][0][0]+f[i-1][0][1])*(m-3)%mod+

					(f[i-1][1][0]+f[i-1][2][0]+f[i-1][2][1])*(m-2)%mod)%mod;

		f[i][2][0]=((f[i-1][0][0]+f[i-1][1][0])*(m-3)%mod+

					(f[i-1][0][1]+f[i-1][0][2]+f[i-1][1][2])*(m-2)%mod)%mod;

		f[i][1][2]=(f[i-1][0][0]+f[i-1][0][1]+f[i-1][2][0]+f[i-1][2][1])%mod;

		f[i][2][1]=(f[i-1][0][0]+f[i-1][0][2]+f[i-1][1][0]+f[i-1][1][2])%mod;

	}

	printf("%lld\n",(f[n][0][0]+f[n][0][1]+f[n][2][0]+f[n][2][1])%mod);

	return 0;

}

100 矩阵快速幂：

//O(49)推矩阵好恶心啊。

#include <cstdio>

#include <algorithm>

#define mod (1000000007)

typedef long long LL;

const int N=1e6+5;

struct Matrix

{

	LL a[7][7];

	Matrix operator *(const Matrix &x)

	{

		Matrix res;

		for(int i=0; i<7; ++i)

			for(int j=0; j<7; ++j)

			{

				LL tmp=0;

				for(int k=0; k<7; ++k)

					tmp+=a[i][k]*x.a[k][j]%mod;

				res.a[i][j]=tmp%mod;

			}

		return res;

	}

}A;

inline Matrix FP(Matrix x,LL k)

{

	Matrix t=x;

	for(--k; k; k>>=1,x=x*x)

		if(k&1) t=t*x;

	return t;

}

int main()

{//[(7*7)^n]*(7*1) 正好转移n次得到f[n+1]。

	freopen("planar.in","r",stdin);

	freopen("planar.out","w",stdout);

	LL n,m; scanf("%lld%lld",&n,&m);

	if(m==2) return putchar(n&1?'0':'2'),0;

/*

0: (0,0)

1: (0,1)

2: (0,2)

3: (1,0)

4: (1,2)

5: (2,0)

6: (2,1)

*/

	if(m>=4) A.a[0][0]=((m-3)*(m-3)%mod-(m-4)+mod)%mod;

	A.a[0][1]=A.a[0][2]=A.a[0][3]=A.a[0][5]=(m-3)*(m-3)%mod;

	A.a[0][4]=A.a[0][6]=(m-2)*(m-3)%mod;

	A.a[1][0]=A.a[1][2]=A.a[2][0]=A.a[2][1]=A.a[3][0]=A.a[3][5]=A.a[5][0]=A.a[5][3]=m-3;

	A.a[1][3]=A.a[1][4]=A.a[1][5]=A.a[2][3]=A.a[2][5]=A.a[2][6]=A.a[3][1]=A.a[3][2]=A.a[3][6]=A.a[5][1]=A.a[5][2]=A.a[5][4]=m-2;

	A.a[4][0]=A.a[4][1]=A.a[4][5]=A.a[4][6]=A.a[6][0]=A.a[6][2]=A.a[6][3]=A.a[6][4]=1;

	A=FP(A,n);

	printf("%lld\n",A.a[4][4]*m%mod*(m-1)%mod);//f[n+1][1][2] = (A^n)[4][j] * Mat={0,0,0,0,m(m-1),0,0}

//	f[1][1][2]=m*(m-1)%mod;

//	LL m3=(m-3)*(m-3)%mod, m2=(m-2)*(m-2)%mod, m23=(m-2)*(m-3)%mod, m34=(m3-m+4+mod)%mod;

//	for(int i=2; i<=n; ++i)

//	{//LONG_LONG_MAX=9e18 > 4e9*1e9

//		f[i][0][0]=(f[i-1][0][0]*m34%mod+

//					(f[i-1][0][1]+f[i-1][0][2]+f[i-1][1][0]+f[i-1][2][0])*m3%mod+

//					(f[i-1][1][2]+f[i-1][2][1])*m23%mod)%mod;

//

//		f[i][0][1]=((f[i-1][0][0]+f[i-1][0][2])*(m-3)%mod+

//					(f[i-1][1][0]+f[i-1][2][0]+f[i-1][1][2])*(m-2)%mod)%mod;

//		f[i][1][0]=((f[i-1][0][0]+f[i-1][2][0])*(m-3)%mod+

//					(f[i-1][0][1]+f[i-1][0][2]+f[i-1][2][1])*(m-2)%mod)%mod;

//

//		f[i][0][2]=((f[i-1][0][0]+f[i-1][0][1])*(m-3)%mod+

//					(f[i-1][1][0]+f[i-1][2][0]+f[i-1][2][1])*(m-2)%mod)%mod;

//		f[i][2][0]=((f[i-1][0][0]+f[i-1][1][0])*(m-3)%mod+

//					(f[i-1][0][1]+f[i-1][0][2]+f[i-1][1][2])*(m-2)%mod)%mod;

//

//		f[i][1][2]=(f[i-1][0][0]+f[i-1][0][1]+f[i-1][2][0]+f[i-1][2][1])%mod;

//		f[i][2][1]=(f[i-1][0][0]+f[i-1][0][2]+f[i-1][1][0]+f[i-1][1][2])%mod;

//	}

	return 0;

}

25分的考场代码：

//Subtask?

#include <map>

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

//#define rg register

#define mod (1000000007)

typedef long long LL;

const int N=1e6+5;

int m,col[N],pw[N];

LL n,tot,Ans;

std::map<int,bool> vis;

inline LL read()

{

	LL now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline LL FP(LL x,LL k)

{

	LL t=1; //x%=mod;

	for(; k; k>>=1,x=x*x%mod)

		if(k&1) t=t*x%mod;

	return t;

}

inline LL Pow(LL x,int k)

{

	for(k--; k--; x*=x);

	return x;

}

inline bool Check(int x,int c)

{

	return ((c==col[x-1]&&x!=n+1)||(x>n&&c==col[x-n])||(x==n&&c==col[1])||(x==tot&&c==col[n+1]))^1;

}

void DFS(int x,int s)

{

	if(x>tot)

	{

		if(!vis[s]) ++Ans;

		return;

	}

	for(int i=1; i<=m; ++i)

		if(Check(x,i)) col[x]=i, DFS(x+1,s+(i-1)*pw[x-1]), col[x]=-1;

}

namespace Subtask4

{

	int f[N][3][3];

	LL Calc(int a,int b)

	{

		for(int i=2; i<=n; ++i)

			for(int j=0; j<3; ++j)

				for(int k=0; k<3; ++k)

					if(j!=k)

					{

						LL tmp=0;

						for(int jj=0; jj<3; ++jj)

							if(j!=jj)

								for(int kk=0; kk<3; ++kk)

									if(k!=kk) tmp+=f[i-1][jj][kk];

						f[i][j][k]=(int)(tmp%mod);

//						f[i][j][k]=tmp%mod;

//						tmp=(j!=0)*((k!=1)*f[i-1][0][1]+(k!=2)*f[i-1][0][2])+(j!=1)*((k!=0)*f[i-1][1][0]+(k!=2)*f[i-1][1][2])+(j!=2)*((k!=0)*f[i-1][2][0]+(k!=1)*f[i-1][2][1]);

					}

		LL ans=0;

		for(int j=0; j<3; ++j)

			for(int k=0; k<3; ++k)

				if(a!=j && b!=k) ans+=f[n][j][k];

		return ans%mod;

	}

	void Main()

	{

//		f[1][0][1]=f[1][0][2]=f[1][1][0]=f[1][1][2]=f[1][2][0]=f[1][2][1]=1;

		LL ans=0;

		for(int a=0; a<3; ++a)

			for(int b=0; b<3; ++b)

				if(a!=b) f[1][a][b]=1, ans+=Calc(a,b), f[1][a][b]=0;

		printf("%d\n",(int)(ans%mod));

	}

}

int main()

{

	freopen("planar.in","r",stdin);

	freopen("planar.out","w",stdout);

//	freopen("table.out","w",stdout);

	n=read(), tot=n<<1, m=read();

	if(m==1) return putchar('0'),0;

	if(m==2) return putchar(n&1?'0':'2'),0;

	if(n<=4 && m<=4)

	{

		pw[0]=1, col[0]=-1;

		for(int i=1; i<=tot; ++i) pw[i]=pw[i-1]*m, col[i]=-1;

		Ans=0, col[1]=1, DFS(2,0), printf("%I64d\n",Ans*m);

		return 0;

	}

	if(m==3) {Subtask4::Main(); return 0;}

	putchar('1');

//	for(m=3; m<=10; ++m)

//		for(n=3; n<=10; ++n)

//			if(FP(m,(tot=n<<1)-1)<=5e7)//n<=4 && m<=4

//			{

//				printf("(%I64d,%d)=",n,m);

//				pw[0]=1, col[0]=-1;

//				for(int i=1; i<=tot; ++i) pw[i]=pw[i-1]*m, col[i]=-1;

//				vis.clear(), Ans=0, col[1]=1, DFS(2,0), printf("%I64d\n",Ans*m);

////				vis.clear(), Ans=0, DFS(1,0), printf("%I64d\n",Ans);

//			}

//			else break;

	return 0;

}

相关文章