程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5155 Harry And Magic Box（組合數學+容斥）

HDU 5155 Harry And Magic Box（組合數學+容斥）

編輯：C++入門知識

HDU 5155 Harry And Magic Box（組合數學+容斥）

Problem Description 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≤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
容斥+組合知識：感謝凡神寫的題解點擊打開鏈接我們首先要保證的是每行都有1，這是前提。然後要想得到答案我們可以枚舉i列全為0（共有C(m,i)選法)，然後就是考慮每行還剩的(m-i)個位置，我們此時可以隨意放置01(2^(m-i)方法)，但是為了保證每行都有1故要減1，此時為(2^(m-i)-1).然後有n行，所以sum[i]=(2^(m-i)-1)^n,然後我們要從裡面剔除一些東西，就是僅僅第i列全為0（注意剛剛i列全為不是僅僅）所以要容斥。ans=sum[0]-sum[1]+sum[2]..#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int maxn=55;
const int MOD=1000000007;
LL c[maxn][maxn];//2^(m-i)-1;
int n,m;
void init()
{
    REPF(i,1,50)
    {
        c[i][0]=c[i][i]=1;
        REPF(j,1,i-1)
           c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
    }
}
LL pow_mod(LL a,int b)
{
    a%=MOD;
    LL ans=1;
    while(b)
    {
        if(b&1)  ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans;
}
int main()
{
    init();
    while(~scanf("%d%d",&n,&m))
    {
        LL ans=0;
        REPF(i,0,m)
        {
            if(i&1)
                ans=(ans-(pow_mod((1LL<<(m-i))-1,n)*c[m][i])%MOD+MOD)%MOD;
            else
                ans=(ans+(pow_mod((1LL<<(m-i))-1,n)*c[m][i])%MOD)%MOD;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

DP寫法：我們考慮dp[i][j]:表示前i行前j列都有1的方案數。dp[i][k]+=dp[i-1][j]*c[m-j][k-j]*c[j][t-(k-j)].t:表示i行選幾個。#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int MOD=1e9+7;
typedef long long LL;
LL c[55][55];
LL dp[55][55];
int n,m;

void init()
{
    for(int i=0;i<=51;i++)
    {
        c[i][0] = 1;
        for(int j=1;j<=i;j++)
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%MOD;
    }
}

int main()
{
    init();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        CLEAR(dp,0);
        dp[0][0]=1;//初始化
        for(int i=1;i<=n;i++)
        {
            for(int k=1;k<=m;k++)
            {
                for(int j=0;j<=k;j++) //保證k>=j
                {
                    for(int t=1;t<=k;t++)
                    {
                        if(k-j>t)   continue;
                        dp[i][k] = (dp[i][k]+dp[i-1][j]*c[m-j][k-j]%MOD*c[j][t-(k-j)]%MOD)%MOD;
                    }
                }
            }
        }
        printf("%I64d\n",dp[n][m]%MOD);
    }
    return 0;
}