hdu 5729 Rigid Frameworks

题意：题目非常长，前面讲了一大堆刚性的和灵活的，但是问的是网格图。很显然网格图不是刚性的（如下图），但是我们可以通过添加对角线使得它变为刚性的，问有多少种添加的方法使变为刚性的。

题解：可以~~(很难)~~发现，在摆动过程中，原来处于同一行的竖边一定平行；同理，原来处于同一列的横边一定平行。我们要做的即为所有横边垂直于所有竖边，那么一行和一列可以分别看做整体。更进一步地，如果两行竖边都垂直于同一列横边，这两行就属于同一个集合。
这里使用一个经典模型，将网格图的行和列作为二分图的左右两个点集，(x,y)连边就表示x行的竖边垂直于y列的横边，那么问题可以转化为最终n+m个点都连通的方案数。但是要注意，连边和添加对角线并不完全等价！添加对角线包含了主对角线和次对角线，而普通的连边没有这种含义。

我们设计一种动态规划（或者说递推），那它必然是总方案数减去不可行的方案数：
$$dp[n][m]=3^{nm}-\sum_{i=1,j=0}^{i<n||j<m} C_{n-1}^{i-1}C_{m}^{j}\cdot dp[i][j]\cdot 3^{(n-i)(m-j)}$$
$3^{nm}$表示对于每一个格子我们总是有无对角线，主对角线，次对角线三种选择。后面的减数项中，为了保证不重复，我们总是枚举左边明确的某一点（例如$1$号点）所在的连通块的左右大小。具体地，我们从$2-n$号点中选出$i-1$个，从$m$个点中选出$j$个，它们内部会有$dp[i][j]$种方案，至于剩下的$n-i$个点和$m-j$个点的关系，任意选择即可。

理解了之后写代码非常简单，可以用预处理做到$O(n^4)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=11;
const int MO=1e9+7;
ll C[N][N],dp[N][N],po3[N*N];

void init()
{
    po3[0]=1;
    for (int i=1;i<N*N;i++) {
        po3[i]=po3[i-1]*3%MO;
    }
    C[0][0]=1;
    for (int i=1;i<N;i++) {
        C[i][0]=C[i][i]=1;
        for (int j=1;j<i;j++) {
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MO;
        }
    }
    for (int n=1;n<N;n++) {
        for (int m=0;m<N;m++) {
            dp[n][m]=po3[n*m];
            for (int i=1;i<=n;i++) {
                for (int j=0;j<=m;j++) {
                    if (i==n&&j==m) continue;
                    dp[n][m]-=C[n-1][i-1]*C[m][j]%MO*dp[i][j]%MO*po3[(n-i)*(m-j)]%MO;
                    dp[n][m]=(dp[n][m]%MO+MO)%MO;
                }
            }
        }
    }
}

int main()
{
    init();
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        printf("%lld\n",dp[n][m]);
    }
    return 0;
}