HDU-5155 Harry And Magic Box(DP，组合数)

￡神魔★判官ぃ 2022-06-09 01:26 146阅读 0赞

## Harry And Magic Box ##

One day, Harry got a magical box. The box is made of n\*m grids. There are sparking jewel in some grids. But the top and bottom of the box is locked by amazing magic, so Harry can’t see the inside from the top or bottom. However, four sides of the box are transparent, so Harry can see the inside from the four sides. Seeing from the left of the box, Harry finds each row is shining(it means each row has at least one jewel). And seeing from the front of the box, each column is shining(it means each column has at least one jewel). Harry wants to know how many kinds of jewel’s distribution are there in the box.And the answer may be too large, you should output the answer mod 1000000007.  
**Input**  
There are several test cases.  
For each test case,there are two integers n and m indicating the size of the box. 0≤n,m≤500≤n,m≤50.  
**Output**  
For each test case, just output one line that contains an integer indicating the answer.  
**Sample Input**  
1 1  
2 2  
2 3  
**Sample Output**  
1  
7  
25

**Hint**  
There are 7 possible arrangements for the second test case.  
They are:  
11  
11

11  
10

11  
01

10  
11

01  
11

01  
10

10  
01

Assume that a grids is ‘1’ when it contains a jewel otherwise not.

题意：给你一个n\*m的箱子，这个箱子里面有许多宝石，这个箱子只能从前面看和从侧面看，并且只能看到最前面的一个，不能看俯视图，已知从侧面看和前面看每一格都有宝石，问这个箱子里的宝石有多少种排列的可能。例如当n=2，m=2的时候，有如Hint里所说的七种可能，1表示有宝石，0表示没宝石。

思路：这题其实就是要保证n\*m的表格中每行每列都至少有一个宝石，假设用DP\[x\]\[y\]来存储x\*y的箱子对应的答案，我们先不考虑列，考虑每一行都一定至少有一个宝石，那么每一行就有C(y,1)+C(y,2)+…+C(y,y)种可能（C表示组合数），根据组合数的公式，这个式子就可以化成pow(2,y)-1。然后因为有x行，所以总的可能性就有S=pow(pow(2,y)-1,x)种。然后我们再来考虑列，我们会发现这S种中有许多是不能满足每列都有宝石的，那么我们只需要把它们找出来，然后用S减去它们就行了。我们先假设有1列是完全没宝石的，那么剩下的y-1列所有的可能性就是DP\[x\]\[y-1\]，再加上这1列有y种选择，所以S要减去y\*DP\[x\]\[y-1\]。那么当有i列是完全没宝石的时候，S要减去C(y,i)\*DP\[x\]\[y-i\]。题目数据只有50，那么我们用记忆化搜索提前打个表就行了。求组合数的时候可以用递推法来求。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 105;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    LL fac[105];
    LL inv[105];
    
    LL POW(LL x, LL y)
    {
        LL ans = 1;
        for (LL i = 1; i <= y; i++)
            ans = (ans*x) % MOD;
        return ans;
    }
    
    LL get_inv(LL n) {
        if (n == 1)
            return 1;
        return get_inv(MOD%n)*(MOD - MOD / n) % MOD;
    }
    
    LL Com(LL n, LL m) {
        return fac[n] * inv[m] % MOD*inv[n - m] % MOD;//求组合数 
    }
    void init() {
        inv[0] = fac[0] = 1;
        for (LL i = 1; i<MAXN; i++) {
            fac[i] = fac[i - 1] * i%MOD;//存阶乘 
            inv[i] = get_inv(fac[i]);//存逆元 
        }
    }
    
    LL DP[55][55];
    
    LL getDP(LL x, LL y)
    {
        if (DP[x][y] != -1)return DP[x][y];
        if (DP[y][x] != -1)return DP[y][x];
        LL ans=1;
        for (LL i = 1; i <= x; i++)
            ans = (ans*(POW(2, y) - 1))%MOD;
        for (LL i = 1; i <= y-1; i++)
        {
            ans = ans - (Com(y, i)*getDP(x, y - i))%MOD;
            ans = (ans%MOD + MOD) % MOD;
        }
        return DP[x][y] = ans;
    }
    
    void init2()
    {
        memset(DP, -1, sizeof DP);
        for (LL i = 1; i <= 50; i++)
        {
            DP[1][i] = 1;
            DP[i][1] = 1;
        }
        for (LL i = 1; i <= 50; i++)
            for (LL j = 1; j <= 50; j++)
                DP[i][j] = getDP(i, j);
    }
    
    int main()
    {
        init();
        init2();
        LL a, b;
        while (scanf("%lld%lld",&a,&b)!=EOF)
            printf("%lld\n", DP[a][b]);
    }