VEXOBEN
Vexoben
Oct 15, 2018
It takes 6 minutes to read this article.

比赛链接:AGC002

D. Stamp Rally

Stamp Rally

E. Candy Piles

题意

n 堆糖果,第 i 堆有 a[i] 个糖果。两人博弈,每次可以取完最大的一堆糖果,或者从所有堆中取走一个糖果,取走最后一颗糖果的输。问均采取最优策略时胜方是谁。

n ≤ 100000, a[i] ≤ 1e9

题解

很奇妙的解法。

先按 a[i] 排个序。在坐标系中画出图标,其中 x = i 的位置有高度为 a[i] 的柱子。

可以发现,拿走最大一堆,就是向右走一个单位;从所有堆中取一个,就是向上走一个单位。从 (0, 0) 开始走。

打个表可以发现斜率为 1 的直线上的点胜负状态相同, 而一个边界上的点,向右向上有一个能走的步数为奇数就是胜态。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
 
int n, a[N];
 
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	int tmp = 1, r = tmp;
	while (tmp < n && a[tmp + 1] >= tmp + 1)
		++tmp;
	while (a[r + 1] >= tmp) ++r;
	int ans = ((a[tmp] - tmp) & 1) || ((r - tmp) & 1);
	puts(ans ? "First" : "Second");
	return 0;
}

F. Leftmost Ball

题意

有 n 种颜色的球,每一种有 k 个。将这 n * k 个球排成一排, 并将所有颜色的最左边的球涂成第 n + 1 种颜色。问最终的颜色序列有多少种可能。

n, k ≤ 2000

题解

不妨假设在最终序列中,每种颜色第一次出现的顺序(也就是这种颜色的第二个球)是1, 2, … ,n , 最后答案再乘以 n! 即可。

考虑dp。令 dp[i][j] 为放了 i 种颜色,且确定了 1, 2, … ,j 变为 n + 1 种颜色的球的出现位置的方案数。

如果下一个球放某种颜色的第一个球, dp[i][j + 1] += dp[i][j]

如果下一个球放某种颜色的第二个球,那么要将这种颜色剩余的 (k - 2) 个球插入到剩余的 ((n - i) * k - (j - i) - 1)个位置中,也就是 dp[i + 1][j] += dp[i][j] * C((n - i) * k - (j - i) - 1, k - 2)

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2005;
const int mod = 1e9 + 7;
 
int n, k;
LL f[N][N], fac[N * N], inv[N * N], fav[N * N];
 
inline void Add(LL &x, LL y) {
	x += y;
	if (x >= mod) x -= mod;
}
 
inline LL C(LL x, LL y) {
	if (x < 0 || x < y) return 0;
	return (fac[x] * fav[y] % mod * fav[x - y] % mod);
}
 
int main() {
	cin >> n >> k;
	if (k == 1) return 0 * puts("1");
	fac[0] = fav[0] = 1;
	fac[1] = fav[1] = inv[1] = 1;
	for (int i = 2; i < N * N; ++i) {
		inv[i] = (-mod / i * inv[mod % i] % mod) + mod;
		fac[i] = fac[i - 1] * i % mod;
		fav[i] = fav[i - 1] * inv[i] % mod;
	}
	f[0][0] = 1;
	for (int i = 0; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			if (j < n) {
				Add(f[i][j + 1], f[i][j]);
			}
			if (i < j) {
				if ((n - i) * k - j + i - 1 >= 0)
					Add(f[i + 1][j], f[i][j] * C((n - i) * k - j + i - 1, k - 2) % mod);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		f[n][n] = f[n][n] * i % mod;
	}
	cout << f[n][n] << endl;
	return 0;
}