hdu 4779 Tower Defense 2013杭州现场赛

  1 /**
  2 题意： 有两种塔，重塔，轻塔。每种塔，能攻击他所在的一行和他所在的一列， 轻塔不 能被攻击，而重塔可以被至多一个塔攻击，也就是说重塔只能被重塔攻击。在一个n*m 的矩阵中，最少放一个塔，可放多个
  3 问，给定p个重塔，q个轻塔，问有多少种放法。。
  4 
  5 思路： 1、 一行中有两个重塔，
  6           2、 一列中有两个重塔
  7           3、 在该行及在该行塔所在的列只有一个塔，重塔或者轻塔。
  8 对以上三种情况
  9 挨个处理：
 10 1、 设有i行有两个重塔，j列有两个重塔，则一共占 i+2*j 行， j+2*i列，共用2*（i+j）个重塔，，因为一行或一列两个塔
 11 2、 对剩余的塔，进行枚举，0<-->剩余的塔，。。，枚举这些塔中重塔的个数进行枚举
 12 
 13 对于1： 在行中有两个重塔 c(n,i)*c(m,2*i)*((2*i)!/2^i)   意思 是在n行中选i行，在m列中选2*i列，  对于选出来的2*i  列，分成i组，需要进行全排列，但是组内不需要进行全排列。。所以为(2*i)!/2^i
 14           在列中有两个重塔，c(m-2*i,j)*c(n-i,2*j)*((2*j)!/2^j)  原理同上
 15 
 16 对于2:设有k个塔， 在剩余的n-(i+2*j) 行  m-(2*i+j) 列中 选 k个 点 ，k最大为  p-2*(i+j)+q
 17      对于k个塔，则重塔最多有b =  min （k， p-2*(i+j) ） 个，  最少有a =  max（0，k-q） 个 
 18      k个塔，最少 a ，最多b  则为（c[k][0]+c[k][1]...+c[k][b]）- (c[k][0]+c[k][1]+...+c[k][a-1])；
 19 最后将不放的情况减掉即可，也就是减1；
 20 注意： 在计算的过程中注意%mod
 21 **/
 22 
 23 
 24 #include <iostream>
 25 #include <algorithm>
 26 using namespace std;
 27 const long long mod = 1000000007;
 28 const int maxn = 220;
 29 const long long R = 500000004;
 30 long long c[maxn][maxn] ;
 31 long long cs[maxn][maxn];
 32 long long sq[maxn];
 33 long long fac[maxn*2];
 34 void init(){
 35     c[0][0] =1;
 36     for(int i=1;i<maxn;i++){
 37         c[i][0] =c[i][i]=1;
 38         for(int j=1;j<i;j++){
 39             c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
 40         }
 41     }
 42     fac[0] =1;
 43     for(int i=1;i<maxn*2;i++)
 44         fac[i] = (fac[i-1]*i)%mod;
 45 
 46     for(int i=0;i<maxn;i++){
 47         cs[i][0] = 1;
 48         for(int j=1;j<=i;j++){
 49             cs[i][j] = (cs[i][j-1]+c[i][j])%mod;
 50         }
 51     }
 52 
 53     sq[0] =1;
 54     sq[1] =1;
 55     long long rr = R;
 56     for(int i=2;i<maxn;i++){
 57         rr = (rr*R)%mod;
 58         sq[i] = (fac[2*i]*rr)%mod;
 59     }
 60 }
 61 
 62 long long cal(long long n,long long m,long long p){
 63     return ((c[n][p]*c[m][2*p])%mod*sq[p])%mod;
 64 }
 65 
 66 long long solve(int z,int x,int y){
 67     if(x>0){
 68         return ((cs[z][y]-cs[z][x-1])%mod+mod)%mod;
 69     }
 70     return cs[z][y]%mod;
 71 }
 72 
 73 int main()
 74 {
 75     init();
 76     int n,m,p,q;
 77     int t;
 78     cin>>t;
 79     while(t--){
 80         cin>>n>>m>>p>>q;
 81         long long  res =0;
 82         for(int i=0;i<=n;i++){
 83             for(int j=0;j<=m;j++){
 84                 if((n>=(i+2*j))&&(m>=(2*i+j))&&((p-2*(i+j))>=0)){
 85                     int tn = n-(i+2*j);
 86                     int tm = m-(2*i+j);
 87                     int tp = p-2*(i+j);
 88                     int tq = q;
 89                     long long ans = (cal(n,m,i)*cal(m-2*i,n-i,j))%mod;
 90                     for(int k=0;k<=tp+tq;k++){
 91                         if(k>min(tn,tm))
 92                             continue;
 93                         int maxp = min(k,tp);
 94                         int minp = max(0,k-tq);
 95                         long long tmp = ((solve(k,minp,maxp)*c[tn][k])%mod*c[tm][k])%mod;
 96                         tmp = (tmp*fac[k])%mod;
 97                         res = (res+tmp*ans)%mod;
 98                     }
 99                 }
100             }
101         }
102         res = ((res-1)%mod+mod)%mod;
103         cout<<res<<endl;
104     }
105     return 0;
106 }