題目位址： http://acm.hdu.edu.cn/showproblem.php?pid=5729
題意：大家都知道矩形是不穩定的，會變成平行四邊形，但是可以在矩形對角線加邊，通過構成三角形使這個矩形穩定下來。給一n*m的矩形，可以在機關矩形裡加兩種對角線（從左上到右下，從左下到右上兩種），或者不加對角線，問使這個n*m的矩形穩定下來的方案數。
思路：說思路前先膜一膜鳥神，是鳥神教會了我這道題……萬分感謝。 多校官方題解是這樣說的：
其實題解已經把思路說好了……隻不過太簡單了吧……蒟蒻很無奈的。 先說題目為什麼可以看做求連通二分圖數目，接着說具體解法。 一. 為什麼可以看做求連通二分圖數目 n*m的矩形有如下性質：對于任意一行，這一行的每一條豎邊永遠保持平行；同樣，對于任意一列，這一行的每一條橫邊永遠保持平行。如題目裡的圖檔所示：
當對一個機關格加上一個斜邊的時候，這個小的機關格的形狀就不能改變，實質上就是組成這個小機關格的橫邊和豎邊保持着一個垂直關系一旦組成這個小單元格的橫邊和豎邊保持了一個垂直關系，那麼和這個橫邊豎邊保持平行關系的變也永遠保持一個垂直關系。 以此，可以把這個問題變為二分連通圖的計數問題，見下圖（自己純手繪的大家輕噴啊……）：
橙色的斜邊，使得組成(1,1)格的上下兩邊（圖中的黃邊）和第一行的所有豎邊（圖中的紅邊）永遠保持垂直關系，以及(1,1)格的左右兩邊和第一列的所有橫邊永遠保持垂直關系（為了不讓圖太混亂，就沒有标出這幾條邊）。對應到二分圖，也是橙色的那條邊，意思是第一行和第一列的所有邊（因為處在同一行的邊永遠互相平行，同一列的邊也是如此）都保持垂直關系。 要使矩形形狀不會發生變化，其實就是任一行和任一列都保持垂直關系。對應到二分圖中，就是由行列的點集組成的二分圖是連通 的。
二.如何通過計算一個二分圖的連通方案數求解 首先，一個n*m的矩陣，由n*m個機關矩陣組成，每個機關矩陣可以加兩種對角線（從左上到右下，從左下到右上兩種），或者不加對角線，共3種選擇，則一個n*m矩陣的總方案數是3^(n*m)，隻要從所有方案中，除去不合法的方案數，就是合法的方案數。這麼做的原因是不合法的方案數更容易求（隻要二分圖是不連通 的，這個方案就是不合法的）。 設dp[n][m]為使n*m矩陣固定下來的合法方案數。 接着，固定一個點（固定這個點是為了防止計數時的重複計算，待會講完讀者回來想想就明白了），為了友善說明，設這個點是n個點中的第一個點（不是m個點中的點）。 枚舉這個點所處連通塊的情況，隻要這個連通塊不包含二分圖中所有的點，則目前的二分圖一定是不連通的，一定是非法方案。 于是狀态轉移方程是：
其中各元素的取值範圍是：1<=n<=10，0<=m<=10，1<=i<=n，0<=j<=m。 試着用一幅圖說明這個方程：
n中的點1固定，當連通塊大小為i，j時，如何計算非法方案數，從n-1個點中選出i-1個點（因為點1已經被固定了），從m個點中選出j個點，用這i，j個點組成連通塊的數量就是
，i+j大小的連通塊有dp[i][j]個合法的存在方案，同時，下面的n-i個點和m-j個點有
個組合方式。 重複一下： 固定一個點，枚舉這個點所處連通塊的情況，隻要這個連通塊不包含二分圖中所有的點，則目前的二分圖一定是不連通的，一定是非法方案。
一些注意事項： 在枚舉i，j的時候，當i==n，j==m的時候，就要停止，不可以讓自己減自己； dp[1][0]應該設為1，代表全二分圖沒有一條邊的情況，是以dp[2][0]……dp[n][0]都得設為0，不然會有重複計算發生，不過我們不需要這樣做，因為在枚舉過程中，dp[2][0]會減去dp[1][0]時的情況，使自己變回0。 注意事項可能說的不好，詳見代碼吧
//不初始化你給我死全家
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MS(x,y) memset(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define lowbit(x) (x&(-x))
typedef long long LL;
inline void fre1(){freopen("input.txt","r",stdin);/*freopen("output.txt","w",stdout);*/}
inline void fre2(){fclose(stdin);/*fclose(stdout);*/}
const int MAXN=30+5;
const double EPS=1e-8;
const int MOD=1e9+7;
LL fact[MAXN*MAXN],C[MAXN][MAXN],dp[MAXN][MAXN];
int main()
{
int n=11;
fact[0]=1;
for(int i=1;i<=n*n;++i) fact[i]=fact[i-1]*3%MOD;
C[0][0]=1;
for(int i=1;i<MAXN;++i){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
}
for(int i=1;i<=10;++i){
for(int j=0;j<=10;++j){
dp[i][j]=fact[i*j];
if(i==1&&j==0) dp[i][j]=1;
for(int ii=1;ii<=i;++ii){
for(int jj=0;jj<=j;++jj){
if(i==ii&&j==jj) continue;
dp[i][j]-=C[i-1][ii-1]*C[j][jj]%MOD*dp[ii][jj]%MOD*fact[(i-ii)*(j-jj)]%MOD;
dp[i][j]=(dp[i][j]%MOD+MOD)%MOD;
}
}
}
}
int m;
while(~scanf("%d%d",&n,&m)) printf("%I64d\n",dp[n][m]);
return 0;
}