首页 > ACM题库 > HDU-杭电 > HDU 4779-Tower Defense-组合数学-[解题报告]HOJ
2015
09-17

HDU 4779-Tower Defense-组合数学-[解题报告]HOJ

Tower Defense

问题描述 :

  DRD loves playing computer games, especially Tower Defense games. Tower Defense is a famous computer game with a number of variations. In general, you are to build some defense towers to guard your territory in this game.
  However, in most Tower Defense games, your defending towers will not attack each other. You will see the shells flying through your towers and finally hit the target on your screen. DRD thinks it to be absurd, and he designed a new tower defense game.
  In DRD’s game, you have two kinds of defending tower, heavy tower and light tower. You can put the tower on a grid with N rows and M columns and each cell in the grid can hold one tower at most. Both two kinds of towers can attack the cells in the same column or the same row as it is located in, and your towers may attack each other. Moreover, light towers should not be attacked by other towers while heavy towers can be attacked by at most one other tower.
  You can put some of your towers (at least one tower) in the grid to build a tower formation satisfying the restriction above. And now, DRD wants you to calculate that how many different tower formations could be designed. Note that all the towers of the same type are considered to be identical. While the answer could be quite large, you should output the number mod (109 + 7).

输入:

  There are multiple test cases in the input. The first line of the input file is an integer T demonstrating the number of test cases. (0< T<= 200).
  For each test case, there is only one line containing 4 integers, N, M, P and Q ,meaning that the grid has N rows and M columns, and you have P heavy towers and Q light towers. You do not have to put all the towers in the grid. (1 <= N, M <= 200, 0 <= P, Q <= 200)

输出:

  There are multiple test cases in the input. The first line of the input file is an integer T demonstrating the number of test cases. (0< T<= 200).
  For each test case, there is only one line containing 4 integers, N, M, P and Q ,meaning that the grid has N rows and M columns, and you have P heavy towers and Q light towers. You do not have to put all the towers in the grid. (1 <= N, M <= 200, 0 <= P, Q <= 200)

样例输入:

3
2 2 0 1
2 2 2 0
3 3 2 1

样例输出:

4
10
144

hdu 4779 Tower Defense

原先以为是哈希+DP没想到超时得不能忍

借鉴了这篇博客的思路 http://www.cnblogs.com/wangsouc/articles/3639137.html

枚举几种状态的种类:2个重型炮同行(占用2列1行)、2个重型炮同列(占用2行1列)、一行1炮(占用1行1列)

其中大数除法用费马小定理求逆元

#include <cstdio>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")  
typedef __int64 ll;
const int MAXN = 205;
const ll mod = 1000000007;
ll AA[MAXN], CC[MAXN][MAXN], POW[MAXN], CM[MAXN][MAXN];
ll niyuan(ll a)
{
	ll res = 1, p = a;
	int n = mod-2;
	while (n)
	{
		if (n & 1) res = res*p%mod;
		p = p*p%mod;
		n >>= 1;
	}
	return res;
}
void init()
{
	int j, i, k;
	for (AA[0] = 1, i = 1; i<= 200; ++i) AA[i] = AA[i-1]*i%mod;
	for (POW[0] = 1, i = 1; i<= 200; ++i) POW[i] = POW[i-1]*2%mod;
	CC[0][0] = 1;
	CM[0][0] = 1;
	for (i = 1; i<= 200; ++i)
	{
		for ( j = 0, k=i/2+1; j<k; ++j)
		{
			CC[i][j] = AA[i]*niyuan(AA[i-j]*AA[j]%mod)%mod;
			CC[i][i-j] = CC[i][j];
		}
		CM[i][0] = 1;
		for ( j = 1; j<=i; ++j)
			CM[i][j] = (CM[i][j-1] + CC[i][j])%mod;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
	int t, N, M, P, Q, i, j, a, b, k, x, mx, mn, pp, qq;
	ll res, s1, s2, s3;
	init();
	scanf("%d", &t);
    while(t--)
    {
		scanf("%d%d%d%d", &N, &M, &P, &Q);
		res = 0;
		for (i=0; i<=N && (i<<1)<=M && (i<<1)<=P; ++i) // 2H_0
		{
			s1 = CC[N][i]*CC[M][i<<1]%mod*AA[i<<1]%mod*niyuan(POW[i])%mod;
			for (j = 0; j<=M-(i<<1) && (j<<1)<=N-i && (j<<1)<=P-(i<<1); ++j) // 2H_1
			{
				s2 = CC[N-i][j<<1]*CC[M-(i<<1)][j]%mod*AA[j<<1]%mod*niyuan(POW[j])%mod * s1;
				s2 %= mod;
				pp = P-2*i-2*j; qq = Q;
				for (a=N-i-2*j,b=M-2*i-j,k=0,x=pp+qq; k<=a && k<=b && k<=x; ++k) // 1L 1H
				{
					mx = min(k, pp);
					mn = max(0, k-qq);
					s3 = s2*(  CC[a][k]*CC[b][k]%mod*AA[k]%mod*(CM[k][mx]-(mn==0?0:CM[k][mn-1]))%mod)%mod;
					//printf("%d..%d..%d..%I64d\n", i,j,k,s3);
					res = (res + s3) % mod;
				}
			}	
		}
		printf("%I64d\n", (res-1+mod)%mod);
    }
    return 0;
}

参考:http://blog.csdn.net/solotzg/article/details/38498791