比赛链接:AGC002
D. Stamp Rally
E. Candy Piles
题意
n 堆糖果，第 i 堆有 a[i] 个糖果。两人博弈，每次可以取完最大的一堆糖果，或者从所有堆中取走一个糖果，取走最后一颗糖果的输。问均采取最优策略时胜方是谁。
n ≤ 100000, a[i] ≤ 1e9
题解
很奇妙的解法。
先按 a[i] 从大到小排个序。在坐标系中画出图标，其中 x = i 的位置有高度为 a[i] 的柱子。
可以发现，拿走最大一堆，就是向右走一个单位；从所有堆中取一个，就是向上走一个单位。从 (0, 0) 开始走。
打个表可以发现斜率为 1 的直线上的点胜负状态相同， 而一个边界上的点，向右向上有一个能走的步数为奇数就是胜态。
UPD: 除了终止态之外，所有斜率为 1 的直线上的点胜负状态相同。所以一个点的状态可以直接推到和一个边界上的点胜负状态相同。要证明这个结论，从两个方面证明. 1、如果一个点是必胜态，它右上角的点不可能是必败态，否则对手下一步一定可以走到右上角的那个点使自己陷入必败态；2、如果一个点是必败态，它右上角的点一定是必胜态。设这个点坐标是 (0, 0)， 那么 (0, 1) 和 (1, 0) 都是必胜态，由 1 的结论得知 (2, 1) 和 (1, 2) 一定是必胜态，从而 (1, 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;
}