题目

Problem Description

在一个n*m的棋盘上，要求每一行每一列都至少有一个棋子的总方案数是多少？由于答案有可能很大，所以输出答案对000000007取模。

Input

两个整数n和m。

1<=n,m<=50

Output

一个整数表示总方案数模1000000007的值。

Sample Input

2 3

Sample Output

25

分析

dp[i][j] 表示刚好有 i 行 j 列满足的方案数。

程序

#include <cstdio> #define Ha 1000000007 long long n,m,C[60][60],dp[60][60]; long long he(int x,int y){ long long ans=1,k=x; for (; y; y>>=1,k=(k*k)%Ha) if (y&1) ans=(ans*k)%Ha; return ans; } void get_C(){ for (int i=1; i<=50; i++){ long long up=1,down=1; for (int j=1; j<=i; j++){ up=(up*(i+1-j))%Ha; down=(down*j)%Ha; long long k=he(down,Ha-2); C[i][j]=(up*he(down,Ha-2))%Ha; } } } int main(){ get_C(); for (int i=0; i<=50; i++) C[i][0]=1; scanf("%d%d",&n,&m); dp[0][0]=1; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++){ for (int k=0; k<j; k++){ dp[i][j]+=(dp[i-1][k]*he(2,k))%Ha*C[m-k][j-k]%Ha; if (dp[i][j]>=Ha) dp[i][j]%=Ha; } dp[i][j]+=(dp[i-1][j]*(he(2,j)-1))%Ha; if (dp[i][j]>=Ha) dp[i][j]%=Ha; } dp[0][0]=0; printf("%lld",dp[n][m]); }