自动搬运

查看原文

来自洛谷，原作者为

	SDLTF_凌亭风 人生的相遇相逢不存在 O(1)，愿每位 OIer 仍在路上

搬运于2025-08-24 22:50:15，当前版本为作者最后更新于2023-09-10 20:59:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解来源于一位和我组队且不愿透露姓名的好兄弟。

这个题有点类似于 2018 年考过的填数游戏。

首先考虑正难则反，也即考虑有多少染色不存在这样的子矩形。注意到，这样的子矩形的特征是两个同色格子在一行或者一列，另两个同色格子在一行或者一列。

所以，这样的矩阵必然满足，对于同行的两个同色格子，这两行其他列的对应位置两个格子必然不一样，列同理。

于是我们直接考虑某一行一种颜色的鸽子就好了，显然一行的某种颜色的格子不可能超过四个，由抽屉原理可以知道，必然在其他行会存在一个同色对，于是一行同色格子最多三个。然而只给了红黄蓝三种颜色，再用一次抽屉原理，当矩形的长或宽超过 $10$ 的时候，必然存在一种颜色出现超过 $4$ 次。由此分析，矩形的长和宽最多为 $9$。

然后写个爆搜就好了。不要认为最多可能状态有 $3^{81}$ 种，首先你可以剪枝，其次你在搜完之后就会发现有值时对应的 $n$ 和 $m$ 非常少，打个表就能过了。

记得特判 $n=1$ 或者 $m=1$ 的情况。

代码

#include<bits/stdc++.h>
using namespace  std;
typedef int ll;
typedef long long int li;
const ll MAXN=3e5+51,MOD=1e9+7;
ll test,n,m,res;
ll c[15][15];
inline ll read()
{
	register ll num=0,neg=1;
	register char ch=getchar();
	while(!isdigit(ch)&&ch!='-')
	{
		ch=getchar();
	}
	if(ch=='-')
	{
		neg=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		num=(num<<3)+(num<<1)+(ch-'0');
		ch=getchar();		
	}
	return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
	ll res=1;
	while(exponent)
	{
		if(exponent&1)
		{
			res=(li)res*base%MOD;
		}
		base=(li)base*base%MOD,exponent>>=1;
	}
	return res;
}
inline void solve()
{
	n=read(),m=read(),n>m?swap(n,m):(void)1;
	if(n==1||m==1)
	{
		return (void)puts("0");
	}
	if(n>=8||m>=8)
	{
		return (void)printf("%d\n",qpow(3,n*m));
	}
	printf("%d\n",(qpow(3,n*m)-c[n][m]+MOD)%MOD);
}
int main()
{
	test=read();
	c[2][2]=66,c[2][3]=390,c[2][4]=1800,c[2][5]=6120,c[2][6]=13680,c[2][7]=15120;
	c[3][3]=3198,c[3][4]=13176,c[3][5]=27000,c[3][6]=13680,c[3][7]=15120;
	c[4][4]=24336,c[4][5]=c[5][5]=4320;
	for(register int i=1;i<=test;i++)
	{
		solve();	
	}
}