?

Description

Input

Output

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*m的矩阵中，假设每一行都存在，对于每一行设i为有i列不存在钻石，那么共有C(m,i)种排列。

对于其他的m-i列中可以放也可以不放，但是要排除全都不放的情况，得到2^(m-i) - 1种，再加上n行得到(2^(m-i)-1)^n

得到f(i) = C(m,i) * (2^(m-i)-1)^n ;

容斥原理排除多余的 f(0) - f(1) + f(2)....f(n) ;

?

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std ; #define MOD 1000000007 #define LL long long LL c[60][60] , num[60][60] , k[60] ; int main() { int i , j , n , m ; memset(num,0,sizeof(num)) ; for(i = 0 ; i <= 50 ; i++) num[i][0] = num[0][i] = 1 ; k[0] = 1 ; for(i = 0 ; i <= 50 ; i++) c[i][0] = 1 ; for(i = 1 ; i <= 50 ; i++) { k[i] = k[i-1] * 2 ; k[i] %= MOD ; } for(i = 1 ; i <= 50 ; i++) { for(j = 1 ; j < i ; j++) { c[i][j] = c[i-1][j-1] + c[i-1][j] ; c[i][j] %= MOD ; } c[i][i] = 1 ; } while(scanf("%d %d", &n, &m) != EOF ) { if( num[n][m] == 0 ) { int temp = 1 ; LL ans = 0 , s ; for(i = 0 ; i <= m ; i++) { s = c[m][i] ; for(j = 1 ; j <= n ; j++) { s *= ( k[m-i]-1 ) ; s %= MOD ; } ans += temp * s ; ans %= MOD ; temp = -temp ; } if( ans < 0 ) ans += MOD ; num[n][m] = num[m][n] = ans ; } printf("%lld\n", num[n][m]) ; } return 0; }
    
   
  

?

?