icpc 7304 Queue of Soldiers

acm dp

由最低的高度開始 dp, dp[i][x] i 是 第幾個高度, 由低至高. x 是有 i 個高度的情況下死了 x 個人

我一開始用了dfs, 果不其然 TLE 了.
之後用dp, 由高的那一邊的想, 發現比較高的人的情況 會 depend on 比較低的人的情況
多虧師兄指教才想通

反思: 如果之後再有這種情況, 應由被依賴的那一邊開始推進

而 nCr 就用 a^m-1 % m = 1 -> a^-1 % m = a^m-2 % m

而解決 TLE 的方法就是加 memorization

icpc7304.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
using namespace std;

const long long MOD = 1000000007;


int heights[50010];
int dheight[1010];
int preSum[1010];

long long dp[1010][1010];

int cmpfunc(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}

long long fac[50010];
long long facr[50010];
long long ncr_cache[50010][1010];
long long fpow(int r) {
	long long result = 1;
	long long a = fac[r];
	long long b = MOD - 2;
	while (b) {
		if (b & 1) {
			result *= a;
			result %= MOD;
		}
		b >>= 1;
		a *= a;
		a %= MOD;
	}

	return result;
}

void make_fac() {
	fac[0] = fac[1] = 1;
	for (int i = 2; i < 50010; ++i)
		fac[i] = (fac[i-1] * i) % MOD;
	for (int i = 0; i < 50010; ++i)
		facr[i] = fpow(i);
}


long long nCr(int n, int r) {
	if (r > n) return 0;
	if (ncr_cache[n][r] != -1) return ncr_cache[n][r];

	long long res = (fac[n] * (facr[r] * (facr[n-r])%MOD) ) % MOD;
	return ncr_cache[n][r] = res;
}

// n height, k die
// dp[i][x] i = i height, x = x die
int dodp(int n, int k) {
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; ++i)
		dp[i][0] = 1;

	for (int i = 1; i < n; ++i)
		for (int j = 1; j <= k; ++j) {
			dp[i][j] = dp[i-1][j];
			int lower_b = min(j, dheight[i]);
			for (int newdie = 1; newdie <= lower_b; ++newdie) {
				dp[i][j] += (dp[i - 1][j - newdie]  * nCr(preSum[i] + newdie - 1, newdie)) % MOD;
				if(dp[i][j] > MOD)
					dp[i][j] %= MOD;
			}
		}
	return dp[n-1][k];
}

void calPreSum(int n) {
	preSum[0] = 0;
	for (int i = 1; i <= n; ++i) {
		preSum[i] = preSum[i - 1] + dheight[i - 1];
	}
}

int main() {
	make_fac();
	memset(ncr_cache, -1, sizeof(ncr_cache));
	int T, N, K;
	int h;
	scanf("%d", &T);
	for (int nt = 1; nt <= T; ++nt) {
		scanf("%d%d", &N, &K);
		for (int nn = 0; nn < N; ++nn)
			scanf("%d", &heights[nn]);

		qsort(heights, N, sizeof(int), cmpfunc);
		int n = -1, v = -1;
		for (int i = 0; i < N; ++i) {
			if (heights[i] != v) {
				v = heights[i];
				++n;
				dheight[n] = 0;
			}
			++dheight[n];
		}
		calPreSum(n);
		printf("Case %d: %lld\n", nt, dodp(n+1, K));
	}
	return 0;
}