HDU4779 Tower Defense 组合数学

原文链接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;

}