题解

#include <stdio.h>

#define MAXN 30010
#define MAXM 135
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000LL;

ll sum[MAXN][7], ho[MAXN][7], ve[MAXN][7], arr[7], h[MAXM][7], dy[65536], id=0, m, vv[20], nxt[7][MAXM][4], g[2][MAXM];
ll f[2][MAXM];

char buf[131072], *cs, *ct;
inline char gc() {
if (csct) {
ct = (cs=buf)+fread(buf,1,131072,stdin);
if (csct) return 0;
}
return cs++;
}
ll read() {
ll r=0; char ch=gc();
while ((ch<'0')||(ch>'9')) ch=gc();
while ((ch>='0')&&(ch<='9')) {
r=r10+ch-'0'; ch=gc();
}
return r;
}
void dfs(ll u, ll cur) { // 枚举所有合法连通性状态
ll i, j;
if (u>m) {
for (i=1; i<=m; ++i) {
if (!sum[m][i]) continue;
ll lp=1, rp=m; // 联通块无交性
while (sum[rp-1][i]sum[m][i]) --rp;
while (!sum[lp][i]) ++lp;
for (j=1; j<=m; ++j) {
if (ij) continue;
if ((sum[rp][j]!=sum[lp][j])&&(sum[rp][j]-sum[lp][j]!=sum[m][j])) return;
}
}
ll hsh=0; ++id;
for (i=1; i<=m; ++i) {
hsh=hsh<<3|arr[i]; h[id][i]=arr[i];
}
dy[hsh]=id; return; // 放入哈希表
}
for (i=1; i<=cur; ++i) { // 联通块无序性
for (j=1; j<=m; ++j) sum[u][j]=sum[u-1][j]+(ij);
arr[u]=i; dfs(u+1,(icur)?cur+1:cur);
}
}
int main() {
ll n=read(), i, j, k, u, d; m=read();
dfs(1, 1);
for (i=1; i<=n; ++i) {
for (j=1; j<m; ++j) ho[i][j]=read();
}
for (i=1; i<=m; ++i) {
for (j=2; j<=n; ++j) ve[j][i]=read();
}
for (u=1; u<=id; ++u) { // 预处理所有转移
for (i=1; i<=m; ++i) vv[i]=0;
for (i=1; i<=m; ++i) {
ll flag = 0;
// 以下 d 表示 h'[j]；vv[d] 表示 h''[j]
for (j=1; j<=m; ++j) { // 排除会孤立 (r-1,c) 的情况
if ((h[u][j]h[u][i])&&(i!=j)) {
flag=1; break;
}
}
// 上左都不连
ll mx=0, hsh=0;
if (flag) {
ll cur=hsh=0;
for (j=1; j<=m; ++j) vv[j]=0;
for (j=1; j<=m; ++j) {
d = (ij)?m:h[u][j]; // (r,c) 是新连通块
if (!vv[d]) vv[d]=++cur;
hsh = hsh<<3|vv[d];
}
nxt[i][u][0] = dy[hsh];
}
// 只连上
nxt[i][u][1] = u; // (r,c) 继承 (r-1,c) 的连通块
if (i1) continue;
// 只连左
if (flag) {
ll cur=hsh=0;
for (j=1; j<=m; ++j) vv[j]=0;
for (j=1; j<=m; ++j) {
d = h[u][j-(ij)]; // (r,c) 继承 (r,c-1) 的连通块
if (!vv[d]) vv[d]=++cur;
hsh = hsh<<3|vv[d];
}
nxt[i][u][2] = dy[hsh];
}
// 上左都连
if (h[u][i]!=h[u][i-1]) { // 防止成环
ll cur=hsh=0;
for (j=1; j<=m; ++j) vv[j]=0;
for (j=1; j<=m; ++j) {
d = (h[u][j]==h[u][i])?h[u][i-1]:h[u][j]; // (r,c) 联通了 (r-1,c) 和 (r,c-1)
if (!vv[d]) vv[d]=++cur;
hsh = hsh<<3|vv[d];
}
nxt[i][u][3] = dy[hsh];
}
}
}
ll o=0, lim=(1<<m-1);
for (i=1; i<=id; ++i) {
f[0][i]=INF; g[0][i]=0LL;
}
for (i=0; i<lim; ++i) { // 特判边界条件，枚举首行水平边状态
ll hsh=1, cur=1; ll w=0LL;
for (j=2; j<=m; ++j) {
if (!(i&(1<<j-2))) ++cur;
else w+=(ll)ho[1][j-1];
hsh = hsh<<3|cur;
}
hsh = dy[hsh];
f[0][hsh]=w; g[0][hsh]=1LL;
}
ll vr[4]; vr[0]=0LL;
for (i=2; i<=n; ++i) {
for (j=1; j<=m; ++j) {
o ^= 1;
for (k=1; k<=id; ++k) {
f[o][k]=INF; g[o][k]=0LL;
}
vr[1]=(ll)ve[i][j]; vr[2]=(ll)ho[i][j-1]; vr[3]=vr[1]+vr[2];
for (k=1; k<=id; ++k) {
if (f[o^1][k]==INF) continue;
for (d=0; d<4; ++d) {
ll v=nxt[j][k][d]; if (!v) continue;
ll w = f[o^1][k]+vr[d];
if (f[o][v]>w) { // 尝试更新后续最优值
f[o][v]=w; g[o][v]=g[o^1][k];
}
else if (f[o][v]==w) {
g[o][v]+=g[o^1][k]; if (g[o][v]>=MOD) g[o][v]-=MOD;
}
}
}
}
}
printf("%d", g[o][1]);
return 0;
}