HDU 5729 Rigid Frameworks

目前还是不能彻底理解这题......

将题意转化成求左边n个点，右边m个点的二分图有几种不同的连边方式将它连通。每条边可以有三种状态（即不选，选红，选蓝，选红选蓝都可以连通，但算两种状态）。

看着这博客学的....http://blog.csdn.net/dpppbr/article/details/51972196

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;

LL mod=1e9+7;
LL dp[15][15],c[15][15],h[120];

LL MOD(LL x) { while(x<0) x=x+mod; return x%mod; }

void pre()
{
    for(int i=0;i<=10;i++) c[i][0]=1;
    for(int i=1;i<=10;i++) for(int j=1;j<=10;j++)
        c[i][j]=c[i-1][j-1]+c[i-1][j];
    h[0]=1; for(int i=1;i<=100;i++) h[i]=(3*h[i-1])%mod;

    memset(dp,0,sizeof dp); dp[1][0]=1;
    for(int i=1;i<=10;i++)
    {
        for(int j=0;j<=10;j++)
        {
            dp[i][j]=h[i*j];
            for(int k=1;k<=i;k++)
            {
                for(int s=0;s<=j;s++)
                {
                    if(i==k&&j==s) continue;
                    LL x=c[i-1][k-1]*c[j][s]%mod;
                    x=x*dp[k][s]%mod;
                    x=x*h[(i-k)*(j-s)]%mod;
                    dp[i][j]=MOD(dp[i][j]-x);
                }
            }
        }
    }
}

int main()
{
    pre(); int u,v;
    while(~scanf("%d%d",&u,&v)) printf("%lld
",dp[u][v]);
    return 0;
}