HDU5155 Harry And Magic Box

Harry And Magic Box

전송문1 전송문2 Oneday, 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
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의 행렬 안에 줄마다 다이아몬드가 있습니다. 다이아몬드의 분포 종류를 물어보세요.

분석하다.

법일
정의 dp[i][j]는 전 i행이 줄마다 최소한 하나의 보석이 있는 조건을 충족시켰고 j열만 보석이 있는 조건을 충족시켰을 경우 몇 가지가 있는지를 나타낸다.i+1 줄에 놓인 보석의 수 k를 매거하면 이 k개 중 t개가 보석이 없는 열에 놓여 있다. 그러면 우리는 이동 방정식을 얻을 수 있다. dp[i+1][j+t]+=dp[i][j][j]\Ctm--j\Ck--tj
법2
f(i)를 각 줄에 i열이 있고 다이아몬드가 없어야 하며 Cim종이 있다고 정의합니다.다른 m-3-i열에는 놓을 수 있지만 모두 놓을 수 없고 n줄이 있다.그리하여
f(i)=Cim∗(2m−i−1)n
종방법.
용척 원리에 근거하여 결과를 얻어내다
ans=f(0)−f(1)+f(2)−......f(n)

CODE

법일

#include
#include
#define mod 1000000007
#define N 55
#define FOR(i,a,b) for(int i=(a),i##_END_=(b);i<=i##_END_;i++)
typedef long long LL;
int n,m;
LL C[N][N],dp[N][N];

int main() {
    C[0][0]=1;
    FOR(i,1,50){
        C[i][i]=C[i][0]=1;
        FOR(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    while(~scanf("%d%d",&n,&m)) {
        memset(dp,0,sizeof dp);
        FOR(i,1,m)dp[1][i]=C[m][i];
        FOR(i,2,n)FOR(k,1,m)FOR(z,0,k)FOR(j,k-z,m-z)
            dp[i][j+z]=(dp[i][j+z]+dp[i-1][j]*C[j][k-z]%mod*C[m-j][z])%mod;
        printf("%lld
",dp[n][m]);
    }
    return 0;
}

법2

#include
#include
#define mod 1000000007
#define N 55
#define FOR(i,a,b) for(int i=(a),i##_END_=(b);i<=i##_END_;i++)
typedef long long LL;
int n,m;
LL C[N][N],pow[N];

int main() {
    pow[0]=C[0][0]=1;
    FOR(i,1,50) {
        C[i][i]=C[i][0]=1;
        pow[i]=(pow[i-1]<<1)%mod;
        FOR(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    while(~scanf("%d %d",&n,&m)) {
        if(n<=1||m<=1) {
            puts("1");
            continue;
        }
        int f=1;
        int ans=0,s;
        FOR(i,0,m) {
            s=C[m][i];
            FOR(j,1,n)s=1LL*s*(pow[m-i]-1)%mod;
            ans=(ans+f*s)%mod;
            f=-f;
        }
        if(ans<0)ans+=mod;
        printf("%d
",ans);
    }
    return 0;
}