AtCoder Grand Contest 045

题目传送门：AtCoder Grand Contest 045。

目录

• A - Xor Battle
• B - 01 Unbalanced
• C - Range Set
• D - Lamps and Buttons
• E - Fragile Balls
• F - Division into Multiples

A - Xor Battle

从后往前分析。令从位置 (i) 开始游戏时，能让 (0) 号玩家获胜的初始数值的集合为 (X_i)。

则 (X_{N + 1} = {0})。如果 (S_i = mathtt{0}) 则 (X_i = X_{i + 1} oplus A_i)；否则如果 (A_i otin X_{i + 1}) 则 (X_i = varnothing) 否则 (X_i = X_{i + 1})。

用异或线性基维护 (X) 即可。

#include <cstdio>

typedef long long LL;
const int MN = 205;

int N;
LL A[MN];
char s[MN];
LL B[64];

int main() {
	int Tests;
	scanf("%d", &Tests);
	while (Tests--) {
		scanf("%d", &N);
		for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
		scanf("%s", s + 1);
		int ok = 1;
		for (int j = 0; j < 60; ++j) B[j] = 0;
		for (int i = N; i >= 1; --i) {
			if (s[i] == '1') {
				LL x = A[i];
				for (int j = 59; j >= 0; --j) if (x >> j & 1) {
					if (B[j]) x ^= B[j];
					else break;
				}
				if (x) { ok = 0; break; }
			} else {
				LL x = A[i];
				for (int j = 59; j >= 0; --j) if (x >> j & 1) {
					if (!B[j]) B[j] = x;
					x ^= B[j];
				}
			}
		}
		puts(ok ? "0" : "1");
	}
	return 0;
}

B - 01 Unbalanced

我们把 0 看成 (+1)，把 1 看成 (-1)。那么就是要让 (0 sim N) 之间所有位置的前缀和的极差最小。

如果我们强制规定前缀和必须大于等于某个值 (M)（前提是存在方案）那么这就相当于固定了前缀和最小值，让前缀和最大值尽量小。

这可以通过很简单的贪心实现：在不违反限制的情况下，从前到后尽量把每个 ? 都变成 1，迫不得已时才变成 0。

这样枚举一波就可以做到 (mathcal O (N^2))，但是它 TLE 了。

同时我们可以求出这个 (M) 最大能到多少合法（把所有 ? 看作 0 后的前缀和最小值），记作 (Z)，不过目前它没用。

注意到当 (M) 增加 (2) 时，最大值也最多增加 (2)，或者也有可能不变（把第一个没变成 0 的 ? 变成 0 即可）。

那么也就是 (M) 越大越好，但是因为这东西是和奇偶性相关的，所以要把 (Z) 和 (Z - 1) 都进行一下 check。

时间复杂度 (mathcal O (N))。

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MN = 1000005;

int N;
char S[MN];

int p[MN];
inline int Solve(int lb) {
	p[N] = 0;
	for (int i = N; i >= 1; --i)
		p[i - 1] = std::max(p[i] + (S[i] == '1' ? 1 : -1), 0);
	int maxval = 0;
	for (int i = 1, now = 0; i <= N; maxval = std::max(maxval, now), ++i)
		if (S[i] == '?') now += now - 1 - p[i] >= lb ? -1 : 1;
		else now += S[i] == '0' ? 1 : -1;
	return maxval;
}

int main() {
	scanf("%s", S + 1), N = strlen(S + 1);
	int minval = 0;
	for (int i = 1, now = 0; i <= N; ++i)
		if (S[i] == '1') minval = std::min(minval, --now);
		else ++now;
	printf("%d
", std::min(Solve(minval) - minval, Solve(minval - 1) - minval + 1));
	return 0;
}

C - Range Set

显然 0 和 1 没有区别，那么不妨假设 (A le B)。考虑如何判断一个序列是否合法。

把操作倒过来考虑，也就是每次选一段连续的 (A) 个 0 或者连续的 (B) 个 1 变成任意字符，问能否变成全 0 串。

显然如果最终序列中甚至不存在上述子串，一定不合法。但是还有其它要求：

试想如果存在连续的 (B) 个 1，注意到 (A le B)，这样的串实际上是一定合法的。

为什么？现在进行正向操作，从左到右填充那一段左边的字符，再从右到左填充那一段右边的字符，操作时互不干扰，只会影响到那一段本身，不会跨过去，最后再把那一段都变成 1 即可。

但是如果只存在连续的 (A) 个 0 却不一定合法，比如当 (A = 2)、(B = 4) 时的 0010。

倒序操作，此时我们需要把连续的 (A) 个 0 变成任意字符，但是只这么做是不行的——你消不掉那些 1。

所以必须要至少做一次把连续的 (B) 个 1 变成任意字符的操作，然而我们已经说明了：只要可以做这样的操作，原串就一定合法。

为了「尽量地满足」这个条件，最好的方法就是把所有连续的，长度 (ge A) 的 0 全都变成 1，如果此时存在连续的 (B) 个 1 就合法。

综上所述，条件就是：把所有连续的长度 (ge A) 的 0 全都变成 1 之后，存在连续的 (B) 个 1。

我们用全部 (2^{N}) 个串减去不合法的就是答案，而不合法的串就是：

由交替的「长度 (< A) 的 0」和「长度 (< B) 的 1，其中可以穿插长度 (ge A) 的 0」构成的串。

有一个坑点就是后者是可以在两端是字符 0 的，但是如果那样就不能和「长度 (< A) 的 0」贴在一起，必须放在整个串的两端。

随便 DP 甚至不需要优化就可以做到 (mathcal O (N A)) 的复杂度了。

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 5005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N, A, B;
int f1[MN], f2[MN], f3[MN], f4[MN];
int g1[MN], g2[MN];

int main() {
	scanf("%d%d%d", &N, &A, &B);
	if (A > B) std::swap(A, B);
	if (A == 1) return printf("%d
", qPow(2, N)), 0;
	f1[1] = 1;
	for (int i = 2; i < B; ++i) {
		f1[i] = 1;
		for (int j = 1; j <= i - 1; ++j)
			f1[i] = (f1[i] + f2[i - j]) % Mod;
		for (int j = A; j <= i - 1; ++j)
			f2[i] = (f2[i] + f1[i - j]) % Mod;
		for (int j = 1; j <= i - 1; ++j)
			f3[i] = (f3[i] + f4[i - j]) % Mod;
		if (i >= A) f4[i] = 1;
		for (int j = A; j <= i - 1; ++j)
			f4[i] = (f4[i] + f3[i - j]) % Mod;
	}
	for (int i = 1; i <= N; ++i) {
		if (i < B) g1[i] = (f1[i] + f3[i]) % Mod;
		for (int j = 1; j < B && j <= i - 1; ++j)
			g1[i] = (g1[i] + (LL)g2[i - j] * f1[j]) % Mod;
		if (i < A) g2[i] = 1;
		for (int j = 1; j < A && j <= i - 1; ++j)
			g2[i] = (g2[i] + g1[i - j]) % Mod;
	}
	int Ans = (g1[N] + g2[N]) % Mod;
	for (int j = 1; j <= N - 1; ++j)
		Ans = (Ans + (LL)g2[N - j] * f2[j]) % Mod;
	printf("%d
", (qPow(2, N) - Ans + Mod) % Mod);
	return 0;
}

D - Lamps and Buttons

对于 Snuke 来说，因为排列 (p) 是均匀随机的，所以任何位置上的灯都是等价的，题目中的「前 (A) 盏灯」也只是为了方便描述。

我们把排列 (p) 拆解成若干不相交循环的乘积。

那么 Snuke 的策略很简单：

1. 随便选取一盏还不知道 (p_i) 的值为多少的，现在还亮着的 (i) 号灯。那么状态变化的灯的编号为 (p_i)。
   • 如果不存在这样的灯，则说明所有灭着的灯无法被点亮，输掉游戏。
   • 如果选完之后它自己灭掉了（(p_i = i)），那就输掉了游戏。
2. 容易发现，此时 (i) 所在循环长度 (ge 2)，可以按顺序依次确定 (p_{p_i}, p_{p_{p_i}}) 等等，然后把它们全部点亮。
3. 如果此时所有灯都被点亮了，Snuke 就赢了，否则回到步骤 1。

为了方便后续转换，我们不妨令步骤 1 中的「随便选取」，变成总是选取编号最小的那一盏灯。

注意：此时 Snuke 的策略已经由随机变成确定性的了，但是他的获胜概率是不变的，那么我们仅需统计哪些排列能让他取胜。

能让 Snuke 取胜的排列必须满足：如果在前 (A) 盏灯中，存在着某一盏灯 (t) 满足 (p_t = t)，那么必须在选到它之前赢得游戏。

那么我们令 (t) 为满足 (1 le t le A) 且 (p_t = t) 的所有编号中最小的那一个，如果不存在这样的灯则 (t = A + 1)。

可以发现，需要满足的就是：考察 (1 le i < t) 的所有灯，它们所在的循环必须覆盖了所有 (A < j le N)。

换句话说，任取 (A < j le N) 都必须满足其所在循环中至少存在一个满足 (1 le i < t) 的元素 (i)。

抽象到这一步已经足够我们进入推式子环节了，在 (2 sim (A + 1)) 之间枚举 (t) 后，一个能让 Snuke 赢得游戏的排列有以下条件：

1. 对于 (1 le i < t)，满足 (p_i e i)。
2. 如果 (t le A)，满足 (p_t = t)。
3. 如果 (t le A)，对于 (t < k le A)，这部分不需要满足任何特殊条件。
4. 对于 (A < j le N)，满足它所在的循环中至少存在一个满足 (1 le i < t) 的元素 (i)。

条件 1 先不管，条件 2 形同虚设，首先考虑条件 3 和条件 4：

令满足 (1 le i < t) 的 (i) 的个数为 (a)，令满足 (A < j le N) 的 (j) 的个数为 (b)，令满足 (t < k le A) 的 (k) 的个数为 (c)。

显然有 (a = t - 1)，(b = N - A)，(c = max(A - t, 0))，相当于求这样的长度为 ((a + c + b)) 的置换个数（忽略条件 1）：

对于任一编号在 ((a + c + 1) sim (a + c + b)) 之间的元素，它所在的置换中必须包含编号在 (1 sim a) 的元素。

前 (a) 个任意置换方案数为 (a!)，依次加入后 (b) 个，必须要插入在已存在的循环内，若当前是第 (i) 个，则有 ((a + i - 1)) 种方案。

最后加入中间的 (c) 个，可以接在之前的任意元素后面，也可以自成新的循环，若当前是第 (i) 个，则有 ((a + b + i)) 种方案。

整理一下，总方案数为 (displaystyle frac{a}{a + b} (a + c + b)!)。

然而条件 1 还没被考虑，此时可能会多统计前 (a) 个元素中的某一个形成了自环的情况，这是需要被剔除的。

所以我们只要使用容斥原理就行啦，容斥一下得到 (displaystyle sum_{d = 0}^{a} {(-1)}^d inom{a}{d} frac{a -d}{a - d + b} (a - d + c + b)!)。

算上前面的枚举 (t)，直接计算即可得到 (mathcal O (N + A^2)) 的时间复杂度。

#include <cstdio>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 10000005, MA = 5005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int Fac[MN], iFac[MN], Inv[MN];
inline void Init(int N) {
	Fac[0] = 1;
	for (int i = 1; i <= N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
	iFac[N] = qPow(Fac[N], Mod - 2);
	for (int i = N; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod; 
	for (int i = 1; i <= N; ++i) Inv[i] = (LL)iFac[i] * Fac[i - 1] % Mod;
}
inline int Binom(int N, int M) {
	return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;
}

int N, A;

int main() {
	scanf("%d%d", &N, &A);
	Init(N);
	int Ans = 0;
	for (int t = 2; t <= A + 1; ++t) {
		int a = t - 1, b = N - A, c = t <= A ? A - t : 0;
		for (int d = 0; d <= a; ++d)
			Ans = (Ans + (d & 1 ? -1ll : 1ll) * Binom(a, d) * Fac[a - d + b + c] % Mod * (a - d) % Mod * Inv[a - d + b]) % Mod;
	}
	printf("%d
", (Ans + Mod) % Mod);
	return 0;
}

E - Fragile Balls

不会。

F - Division into Multiples

不会。