原文链接https://www.cnblogs.com/zhouzhendong/p/HDU4779.html
题目传送门 - HDU4779
题意
$T$ 组数据。
给定一个 $n\times m$ 的棋盘，要在上面放最多 $P$ 个重塔和最多 $Q$ 个轻塔。
每一个塔都会攻击同行和同列的塔。轻塔不能承受任何攻击。重塔最多可以承受一个塔的攻击。
所有重塔全是一样的，所有轻塔也是一样的，但是重塔和轻塔不同。
现在问你有多少放置塔（至少放一个塔）的方案。答案对于 $1e9+7$ 取模。
$1\leq T,n,m,P,Q\leq 200$
题解
听说这一题 Cyanic 读错两次题意还出了一道毒瘤题给我们阿掉他的机会？？
我们写考虑枚举有两个重塔的行和列的个数。
假设上面的两个量分别为 $i$ 和 $j$ 。
则剩余行数和列数分别为 $n-i-2j$ 和 $m-2i-j$ ，剩余重塔个数为 $P-2i-2j$ 。
我们可以预处理 $dp_{i}{j}$ 为在 $i$ 个行或列中选择 $j$ 对 行或列 的方案数。
则显然答案为 $\binom{i}{2j}\ \ \ \ \ \ \ \ \times \ \ \ \ \ \ \ \ (2j)! \ \ \ \ \ \ \ \ ÷ \ \ \ \ \ \ \ \ 2^{j}$
表示的意义： $i$ 行选 $2j$ 行 全排列 并依次选择每一对行或列 每一对行或列都有两种排列方式，总共被算了 $2^{j}$ 次，要除掉。
然后枚举在剩余的 $n-i-2j$ 行和 $m-2i-j$ 列中放多少个塔。
需要预处理一下组合数的前缀和。
然后可以用组合数算出当前情况对答案的贡献。具体自己看代码吧。这里不展开赘述。
注意一下，要特判掉不放塔的情况。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=405,mod=1e9+7;
int T,n,m,P,Q;
int C[N][N],Fac[N],Pow[N],s[N][N],dp[N][N];
int main(){
Fac[0]=Pow[0]=1;
for (int i=0;i<N;i++)
C[i][0]=s[i][0]=1;
for (int i=1;i<N;i++)
Fac[i]=1LL*Fac[i-1]*i%mod,Pow[i]=1LL*Pow[i-1]*500000004%mod;
for (int i=1;i<N;i++)
for (int j=1;j<=i;j++){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
s[i][j]=(s[i][j-1]+C[i][j])%mod;
}
for (int i=0;i<N/2;i++)
for (int j=0;j<N/2;j++)
dp[i][j]=1LL*C[i][j*2]*Fac[2*j]%mod*Pow[j]%mod;
scanf("%d",&T);
while (T--){
scanf("%d%d%d%d",&n,&m,&P,&Q);
int ans=0;
for (int r=0;r*2<=m;r++)
for (int c=0;c*2<=n;c++){
int RR=n-c*2-r,CC=m-r*2-c,p=P-r*2-c*2;
if (RR<0||CC<0||p<0)
continue;
int mi=min(RR,CC),ma=max(RR,CC);
int Mul=1LL*C[n-2*c][r]%mod*C[m-2*r][c]%mod*dp[m][r]%mod*dp[n][c]%mod;
int tot=0,lim=min(mi,p+Q);
for (int i=0;i<=lim;i++){
int M2=s[i][min(p,i)];
if (max(i-Q,0)-1>=0)
M2=(M2-s[i][max(i-Q,0)-1]+mod)%mod;
if (r||c||i)
tot=(1LL*M2*C[ma][i]%mod*C[mi][i]%mod*Fac[i]+tot)%mod;
}
ans=(1LL*Mul*tot+ans)%mod;
}
printf("%d\n",ans);
}
return 0;
}