HDU 5155 Harry And Magic Box dp

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5155

题意：

给n*m的零一矩阵，问它的左视图和正视图都为全1的所有情况。

题解：

n，m不超过50，所以可以跑O(n^4)；

另dp[i][j]代表前i行（每一行至少放一个，因为这样就可以只考虑列会不会为空就可以了）中有j列不全为0，那么有状态转移方程：

dp[i][k]+=dp[i-1][j]*C[m-j][k-j]*C[j][t]（0<=t<=j）

C[i][j]表示i个方格中j个为1的所有情况。（组合数，可递推离线处理出来）

（题外话：原先以为要和TSP一样，要用集合来表示状态，但其实它这里填的位置不连续其实没有影响，因为它等价于连续的情况。）

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
typedef __int64 LL;

const int maxn = 55;
const int mod = 1e9 + 7;

int n, m;
LL dp[maxn][maxn];

LL C[maxn][maxn];
void get_c() {
    for (int i = 0; i < maxn; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
}

void init() {
    memset(dp,0,sizeof(dp));
}

int main() {
    get_c();
    while (scanf("%d%d", &n, &m) == 2 && n) {
        init();
        for (int j = 1; j <= m; j++) dp[1][j] = C[m][j];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = j; k <= m; k++) {
                    for (int t = 0; t <= j; t++) {
                        if (k == j&&t == 0) continue;
                        dp[i][k] += dp[i - 1][j] * C[m - j][k - j] % mod*C[j][t] % mod;
                        dp[i][k] %= mod;
                    }
                }
            }
        }
        printf("%lld
", dp[n][m]);
    }
    return 0;
}