题意：
对于一个由n*m个1*1的菱形组成可任意扭曲的矩形(姑且这么说)，求添加斜线*(两种)让菱形变成正方形，使得整个矩形固定且无法扭曲的方案数。
分析：
n*m的矩形有如下性质：( 平行具有传递性 )
任意一行的每一条竖边永远保持平行,任意一列的每一条横边永远保持平行
当一个单位格加上斜边的时候，这个单位格的形状就不能改变，实质上就是组成这个单位格的横边和竖边保持着一个垂直关系.
一旦组成这个小单元格的横边和竖边保持了一个垂直关系，那么横边所在的列和竖边所在的行均能保持垂直关系.
即任意一行和任意一列均为一个整体。
那么题意即为使任意列的横边和任意行竖边均保持垂直关系
还有二维平面上两列横边若垂直同一行竖边，则两列横边互相平行，即它们可以看做一个整体(属于同一个集合)
于是，将纵边抽象为点集(size为行数)，将横边抽象为点集(size为列数)，垂直关系抽象为连线，即求连通二分图的方案数。
转移方程式:
DP[n][m] = 3^(n*m) - ∑( DP[i][j] * C[i-1][n-1] * C[j][m] * 3^( (n-i)*(m-j) ) ) (i!=n||j!=m);
意为，所有状态数 - 两点集中选取(i,j)个点在同一个连通块内，剩下的点任意状态
注意点：
1.必须枚举固定的一个点所在的连通块情况以避免计数重复, 那么这个连通块有一个点是确定的了，所以，共 i 条横边的枚举为 C[i-1][n-1]，且i,j是等价的，故只选择其中任意一边就可以了
2.另外，因为选择的是 所有情况 - 不合理情况 的计数方法，不合理情况至少有两个以上的连通块连通块内，故 i==n且j==m 的情况为合法情况，此时该退出循环
了解来龙去脉之后，代码就显得不那么重要了。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD = ;
long long C[][],pow3[];//组合数,幂
long long dp[][];
void Init()
{
C[][]=;
for(int i = ; i <= ; i++){//组合数 C[下标][上标]
C[i][] = C[i][i] = ;
for(int j = ; j < i; j++)
C[i][j] = (C[i-][j] + C[i-][j-]) % MOD;
}
pow3[] = ;
for(int i = ; i <= ; i++) //3的幂
pow3[i] = * pow3[i-] % MOD;
}
void CalDP()
{
dp[][] = dp[][] = ; //重要的边界条件，一个点时必然联通且方案唯一
long long tmp;
for(int i = ; i <= ; i++)
{
for(int j = ; j <= ; j++)
{
// if(i==1||j==1) continue;
dp[i][j] = pow3[i * j];//总数目
for(int ii = ; ii <= i; ii++)//至少有自己
{
for(int jj = ; jj <= j; jj++)
{
if(ii == i && jj == j) continue;
tmp = C[i-][ii-] * C[j][jj] % MOD;
tmp = tmp * dp[ii][jj] % MOD;
tmp = tmp * pow3[ (i-ii)*(j-jj) ]%MOD;
dp[i][j] = (dp[i][j] - tmp + MOD) % MOD;
}
}
}
}
}
int main()
{
Init();
CalDP();
int n,m;
while(~scanf("%d%d",&n,&m))
{
printf("%lld\n",dp[n][m]);
}
}