原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1634.html
考虑到加一条斜着的边的作用是让一个格子的行和列垂直。
我们需要让所有的行和列都互相垂直。于是，只要我们建一个二分图，行和列分居两侧，问题就被转化成了统计连通的二分图个数，其中，一条边有两种连接的方式。
令 $dp_{i,j}$ 表示左边有 $i$ 个，右边有 $j$ 个节点 的连通二分图个数，于是我们需要补集转化一下，得到：
$$dp_{n,m}=3^{nm}\sum_{i=1}^{n}\sum_{j=0}^{m}[i\neq n\ {\rm OR}\ j\neq m] \binom{n-1}{i-1}\binom{m}{j}\cdot 3^{(n-i)(m-j)}dp_{i,j}$$
这里略微的解释一下意义。我们枚举第一个节点所在的连通块的左右部分点的个数，然后剩余的边可以随意连，所以有一个 $3^{(n-i)(m-j)}$ 。
#include <bits/stdc++.h>
using namespace std;
const int N=15,mod=1e9+7;
int C[N][N],Pow3[N*N],dp[N][N];
int main(){
for (int i=0;i<N;i++)
C[i][0]=C[i][i]=1;
for (int i=1;i<N;i++)
for (int j=1;j<i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
Pow3[0]=1;
for (int i=1;i<N*N;i++)
Pow3[i]=3LL*Pow3[i-1]%mod;
memset(dp,0,sizeof dp);
dp[0][1]=dp[1][0]=1;
for (int n=1;n<N;n++)
for (int m=1;m<N;m++){
dp[n][m]=Pow3[n*m];
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++)
if (i!=n||j!=m)
dp[n][m]=(-1LL*C[n-1][i-1]*C[m][j]%mod
*Pow3[(n-i)*(m-j)]%mod*dp[i][j]%mod
+dp[n][m])%mod;
dp[n][m]=(dp[n][m]+mod)%mod;
}
int n,m;
while (~scanf("%d%d",&n,&m))
printf("%d\n",dp[n][m]);
return 0;
}
原文：https://www.cnblogs.com/zhouzhendong/p/51Nod1634.html