Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 1025 Accepted Submission(s): 297
因为重塔有两种放法...其中一种是和轻塔一样的，所以可以视为轻塔...
我们枚举有i行被两个棋子所占，j列被两个棋子所占...那么总占用行数为i+2*j，列数为j+2*i，使用重塔数为(i+j)*2，这个的方案数可以用组合数学搞定：c[n][i]*c[m][i<<1]*(i<<1)!/(2^i)...这是行的算法...列的算法是一样的...c[n][i]*c[m][i<<1]就不用说了...后面的就是我们从网格中选出i组列，每一组是绑定的两列，所以是(i<<1)!/(2^i)...
然后剩下的n-(i+2*j)行和m-(j+2*i)列中选出k行k列方轻塔和重塔，应该是c[n-(i+2*j)][k]*[m-(j+2*i)][k]*(重塔方案数)...
我们求出重塔的数量范围：Min=max(0,k-q),Max=min(k,p-2*(i+j))...所以重塔的方案数应该是c[k][Max]-c[k][Min-1]...
然后乘起来加一加就好了...
WA了好久...都是细节...
首先是2^i不能直接1LL<<i，而要预处理...因为i可能等于200...
然后阶乘要预处理到400...
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define int long long
using namespace std;
//眉眼如初，岁月如故
const int maxn=400+5,Mod=1e9+7;
int n,m,p,q,cas;
long long ans,c[maxn][maxn],po[maxn],fac[maxn],sum[maxn][maxn];
inline long long power(long long x,int y){
long long res=1;
while(y){
if(y&1)
(res*=x)%=Mod;
(x*=x)%=Mod,y>>=1;
}
return res;
}
signed main(void){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%lld",&cas);c[0][0]=sum[0][0]=1;
for(int i=1;i<=400;i++)
c[i][0]=1,c[i][i]=1,sum[i][0]=1;
for(int i=1;i<=400;i++)
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
for(int i=1;i<=400;i++)
for(int j=1;j<=i;j++)
sum[i][j]=(sum[i][j-1]+c[i][j])%Mod;
fac[0]=1,po[0]=1;
for(int i=1;i<=400;i++)
fac[i]=fac[i-1]*i%Mod,po[i]=po[i-1]*2%Mod;
while(cas--){
scanf("%lld%lld%lld%lld",&n,&m,&p,&q);ans=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(i+2*j<=n&&j+2*i<=m&&2*(i+j)<=p){
long long tmp=c[n][i]*c[m][2*i]%Mod*fac[i<<1]%Mod*power(po[i],Mod-2)%Mod;
(tmp*=c[m-i*2][j]*c[n-i][2*j]%Mod*fac[j<<1]%Mod*power(po[j],Mod-2)%Mod)%=Mod;
long long lala=0LL;
for(int k=0;k<=p-2*(i+j)+q;k++)
if(k<=n-(i+2*j)&&k<=m-(j+2*i)){
int Max=min(k,p-2*(i+j)),Min=max(0LL,k-q);
long long s;
if(Min==0LL)
s=0LL;
else
s=sum[k][Min-1];
(lala+=c[n-(i+2*j)][k]*c[m-(j+2*i)][k]%Mod*fac[k]%Mod*((sum[k][Max]-s+Mod)%Mod)%Mod)%=Mod;
}
(ans+=tmp*lala%Mod)%=Mod;
}
printf("%lld\n",(ans-1+Mod)%Mod);
}
return 0;
}//Cap ou pas cap. Pas cap.
By NeighThorn
原文：http://www.cnblogs.com/neighthorn/p/6284392.html