代码

#include<algorithm>
#include<cstdio>
#define F dp[i+1][p][l]
using namespace std;
const int mod=1e9+7;
int n,m,s,x,y,mn,mx,num,ans,dp[10][550][10];
int pow(int k,int i)
{
	int t=1;
	while(i)
	{
		if(i&1) t=1ll*t*k%mod;
		k=1ll*k*k%mod;i>>=1;
	}
	return t;
}
int main()
{
	scanf("%d%d",&n,&m);
	if(n>m) swap(n,m);
	mn=min(n+1,m);s=(1<<n-1)-1;
	for(int i=0;i<(1<<n);++i) dp[1][i][0]=1;
	for(int i=1;i<mn;++i)
		for(int j=0;j<(1<<n);++j)
			for(int k=0;k<n;++k)
				if(dp[i][j][k])
					for(int p=0,l;p<(1<<n);++p)
					{
						if(((j>>1)&p)!=(p&s)) continue;
						if(k&&((j>>n-k+1)!=((p>>n-k)&((1<<k-1)-1)))) continue;
						l=n-1;
						for(;l>k;--l)
							if(((j>>n-l)&1)==((p>>n-l-1)&1))
								break;
						F+=dp[i][j][k];
						if(F>=mod) F-=mod;
					}
	for(int i=0;i<(1<<n);++i)
		for(int j=0;j<n;++j)
		{
			ans+=dp[mn][i][j];
			if(ans>=mod) ans-=mod;
		}
	printf("%d\n",1ll*ans*pow(3-(n==1),m-mn)%mod);
	return 0;
}

评测结果