问题描述： 一个盒子由 n∗m 个格子组成，有一些格子里会有闪闪发光的宝石。 现在有求盒子从左边看过去，每一行都闪烁着光芒，从前面看过去，每一列也都闪烁着光芒。 问：盒子里的宝石有多少种分布情况。 答案有可能很大，所以输出答案对 1000000007 取模。
输入描述： 多组输入数据 每组数据一行，输入两个数 nm 表示盒子的大小， 0≤n,m≤50
输出描述： 每组数据输出一行，一个整数，代表方案数
官方题解： dp 题，我们一行一行的考虑。 dp[i][j] ,表示前i行，都满足了每一行至少有一个宝石的条件，而只有j列满足了有宝石的条件的情况有多少种。枚举第i+1行放的宝石数k，这k个当中有t个是放在没有宝石的列上的，那么我们可以得到转移方程： dp[i+1][j+t]+=dp[i][j]∗c[m−j][t]∗c[j][k−t] ，其中 c[x][y] ，意为在x个不同元素中无序地选出y个元素的所有组合的个数。 dp 主要是找转移方程，找到了就简单。找不到就卡到死T_T。
还有一种解法是用排列组合加容斥，而且找博客的时候还看到好多用这种解法的，果然还是大神比较多。不过dp还是比较简单的。
看了别人的博客上的图讲的还挺清楚： 情况1:
情况2:
综上两种情况，得到状态转移公式： dp[i][j]+=dp[i][j−1]∗(2i−1)+dp[i−k][j−1]∗c[k][i]∗ (2 ^ (i−k))
AC代码：
也可以在 while() 外直接把 dp 的表打出来。
#include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cstring> using namespace std; #define ll long long const int mod=1e9+7; ll mod_pow(ll a,ll n,ll p) { ll ret=1,A=a; while(n) { if (n & 1) ret=(ret*A)%p; A=(A*A)%p; n>>=1; } return ret; } ll c[55][55];///组合数 ll dp[55][55]; ll pow[55];///2的i次方 int main() { // freopen("in.in","r",stdin); // freopen("test.out","w",stdout); int n,m; pow[0]=1; for(int i=1;i<55;i++) { pow[i]=(pow[i-1]*2)%mod; } c[0][0]=1; for(int i=1;i<=55;i++) { c[i][0]=1; c[i][i]=1; for(int j=0;j<=i;j++) { c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } } while(~scanf("%d%d",&n,&m)) { if(n==0||m==0) printf("0\n"); else if(n==1||m==1) { printf("1\n"); } else { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][1]=1; for(int i=2;i<=m;i++) dp[1][i]=1; for(int i=2;i<=n;i++) { for(int j=2;j<=m;j++) { dp[i][j]=(dp[i][j-1]*(pow[i]-1)%mod+mod)%mod; for(int k=1;k<i;k++) { dp[i][j]=((dp[i][j]+(dp[i-k][j-1]*c[i][k])%mod*pow[i-k]%mod)+mod)%mod; } } } printf("%I64d\n",dp[n][m]); } } return 0; }