( ext{Solution:})
题目标签是(dp,)但是纯暴力打表找规律可以有(65)分。
首先是对于(O(2^{nm}*nm))的暴力搜索，显然都会。
考虑几条性质：
-
每一条由左下到右上的对角线需要非严格单调递减。
-
若(a[i][j-1]=a[i-1][j])则以(a[i][j])为左上角的矩阵填的数必须相等。
证明：
对于第一条，若不满足这条性质，则必然存在一个路径，(R o 1,D o 0)使得其不满足题意。
对于第二条，首先满足(R o x,D o x,)则对于后面的所有路径，若有一个不相等的则必然存在一条路径(D o Big)或(R o Small)使得题目不成立。
于是，设(a[i][j])表示第(j)列(i o n)行数字的状压结果，(b[i][j])表示以((i,j))为左上角的矩阵的数字是不是相等。
考虑每次填数完毕就判断一次。若矩阵相等，则( ext{b[i][j]=b[i][j+1]&&(a[i][j+1]>>1)==a[i+1][j]})
然后对角线是( ext{x<n&&y>1&&g[x][y]==g[x+1][y-1]&&!b[x+1][y](False)})
代码中保证只有上一次填了(1)下一次才能继续填。否则必须填(0).从而起到了剪枝的效果。
于是可以打表，继续找规律：
int A[9][9]= {
{0,0,0,0,0,0,0,0,0},
{0,2,4,8,16,32,64,128,256},
{0,0,12,36,108,324,972,2916,8748},
{0,0,0,112,336,1008,3024,9072,27216},
{0,0,0,0,912,2688,8064,24192,72576},
{0,0,0,0,0,7136,21312,63936,191808},
{0,0,0,0,0,0,56768,170112,510336},
{0,0,0,0,0,0,0,453504,1360128},
{0,0,0,0,0,0,0,0,3626752},
};
观察一下，上半个矩阵中，有很多值满足(a[i][j]=a[i][j-1]*3.)
所以，特判掉(n=m)的情况后，直接调用(A(n,n+1))并使用快速幂即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,R=10879488;
int A[9][9]= {
{0,0,0,0,0,0,0,0,0},
{0,2,4,8,16,32,64,128,256},
{0,0,12,36,108,324,972,2916,8748},
{0,0,0,112,336,1008,3024,9072,27216},
{0,0,0,0,912,2688,8064,24192,72576},
{0,0,0,0,0,7136,21312,63936,191808},
{0,0,0,0,0,0,56768,170112,510336},
{0,0,0,0,0,0,0,453504,1360128},
{0,0,0,0,0,0,0,0,3626752},
};
const int mod=1e9+7;
inline int add(int x,int y) {
return (x+y)%mod;
}
inline int mul(int x,int y) {
return 1ll*x*y%mod;
}
namespace P3 {
inline int qpow(int x,int y) {
int res=1;
while(y) {
if(y&1)res=mul(res,x);
x=mul(x,x);
y>>=1;
}
return res;
}
void solve() {
if(n>m)swap(n,m);
if(n==m)printf("%d
",A[n][m]);
else {
if(n==1) {
printf("%d
",qpow(2,m));
return;
}
int c=m-n;
if(n<8)R=A[n][n+1];
printf("%d
",mul(R,qpow(3,c-1)));
}
}
}
namespace Biao {
int a[13][13],g[30][30],ans=0;
bool b[100][100];
bool check(int x,int y) {
a[x][y]=a[x+1][y]|(g[x][y]<<(n-x));
if(y==m)b[x][y]=1;
else b[x][y]=b[x][y+1]&&(a[x][y+1]>>1)==a[x+1][y];
if(x<n&&y>1&&g[x][y]==g[x+1][y-1]&&!b[x+1][y])return false;
return true;
}
void dfs(int x,int y) {
if(y<1) {
dfs(x-1,m);
return;
}
if(x<1) {
ans++;
return;
}
if(x==n||y==1||g[x+1][y-1]==1) {
g[x][y]=1;
if(check(x,y))dfs(x,y-1);
}
g[x][y]=0;
if(check(x,y))dfs(x,y-1);
}
void solve() {
ans=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(g,0,sizeof(g));
if(n>m)swap(n,m);
dfs(n,m);R=ans;
}
}
int main() {
scanf("%d%d",&n,&m);
P3::solve();
return 0;
}
参考：https://www.luogu.com.cn/blog/2003ok/solution-p5023 Lisy_03 的博客
（侵删）
总结：数据范围小所想到的状压(dp)并不一定正确，在不会正解的情况下先写暴力打表。