E. Game with Binary String 详细题解

问题理解

我们有一个二进制字符串（只包含 $0$ 和 $1$）。两名玩家轮流操作，第一名玩家先手。

操作规则：

• 每次必须选择两个相邻的字符删除（第一个和最后一个字符也视为相邻，即字符串是环形的）
• 第一名玩家只能删除两个 $0$
• 第二名玩家只能删除至少包含一个 $1$ 的两个相邻字符（即 $(0,1)$、$(1,0)$ 或 $(1,1)$）
• 无法操作（字符串长度小于 $2$）的玩家输

给定长度为 $n$ 的字符串 $s$，需要计算有多少个子串 $s[l..r]$（连续子串，不是环形，是普通的线性子串），使得在该子串上进行游戏时，第一名玩家有必胜策略。

---

关键观察

1. 游戏与奇偶性、数量的关系

将 $0$ 视为某种“资源”，$1$ 视为另一种。由于第一名只能删 $00$，第二名可以删包含 $1$ 的对，所以 $1$ 的数量会影响第二名能操作的次数。

设：

• $cnt_0$ = 字符串中 $0$ 的数量
• $cnt_1$ = 字符串中 $1$ 的数量

每次操作减少 $2$ 个字符。游戏总操作次数取决于谁无法继续。

2. 转化为公平组合游戏

一个重要思路：考虑每次操作对某种“势能”的影响。可以将字符串看作一个序列，定义某种不变量。

观察标程，它定义了一个前缀和：

$$p[i] = \#0\text{ up to }i - 3 \times \#1\text{ up to }i $$

更准确地说，令：

$$p[0] = 0$$ $$p[i+1] = p[i] + (s[i] == '1' ? -3 : 1)$$

即遇到 $0$ 时 $+1$，遇到 $1$ 时 $-3$。

这个看似奇怪的定义，实际上是为了将游戏结果转化为关于 $p$ 值的比较问题。

---

3. 核心结论（来自标程逻辑）

标程计算的是：

$$\sum_{i=0}^{n} \sum_{j=0}^{3} \#\{ \text{之前的 } p \text{ 值满足 } p[prev] \le p[i] - threshold[(i-j) \bmod 4] \} $$

其中 $threshold = [0, 1, 1, -2]$。

这说明：子串 $s[l..r]$ 是第一玩家必胜当且仅当某个关于 $p$ 的条件成立。

经过分析（可以结合 Sprague–Grundy 或配对策略），可以得到：

---

4. 必胜条件

定义 $f(i) = p[i]$ 如上。对于子串 $s[l..r]$（对应 $p$ 的区间 $[l-1, r]$），第一玩家必胜当且 only 当：

$$p[r] - p[l-1] > \text{某个依赖于长度模 4 的阈值}$$

更精确地，设 $len = r-l+1$，$m = len \bmod 4$，则条件为：

$$p[r] - p[l-1] > t_m$$

其中：

• $t_0 = 0$
• $t_1 = 1$
• $t_2 = 1$
• $t_3 = -2$

（注意 $t_m$ 实际上等于 $-threshold[m]$ 或类似调整，标程中用的是 $bound = p[i] - threshold[len]$）

---

5. 为什么这样定义？

考虑一个简化版本：如果只能删 $00$（没有第二名），那么 $0$ 的数量决定了胜负：偶数个 $0$ 则后手胜？实际上需要更细致的分析。

引入 $1$ 后，第二名每次操作消耗至少一个 $1$，同时也会消耗一个 $0$ 或另一个 $1$。通过分析奇偶性和 $0$、$1$ 的数量关系，可以证明：

将每个 $1$ 视为“-3”的权重，$0$ 视为“+1”，那么子串的和 $p[r]-p[l-1]$ 与子串长度模 $4$ 共同决定了胜负。这是通过模拟小长度字符串的胜负状态发现的规律，然后归纳证明。

---

6. 算法实现（标程解析）

标程做法：

• 计算前缀和 $p[0..n]$，$p[0]=0$，$p[i+1]=p[i] + (s[i]=='1'?-3:1)$
• 用 $4$ 个树状数组（或线段树）trees[0..3]，每个维护对应下标模 $4$ 的 $p$ 值的出现次数
• 遍历 $i=0..n$：
  • 对于 $j=0..3$（$j$ 表示 $i \bmod 4$ 对应的某个分类）：
    • $len = (i - j + 4) \bmod 4$
    • $bound = p[i] - threshold[len]$
    • 查询 trees[j] 中值 $\le bound$ 的个数，累加到答案
  • 将 $p[i]$ 插入到 trees[i % 4] 中

这样统计的是所有 $l \le i$ 且 $r = i$ 的合法子串。最终 $ans$ 即为所有合法子串数。

---

7. 复杂度分析

• 前缀和计算 $O(n)$
• 每个 $i$ 进行 $4$ 次查询和 $1$ 次插入，每次 $O(\log S)$，其中 $S$ 是 $p$ 的值域范围（$p$ 的范围大约是 $[-3n, n]$，即 $O(n)$）
• 总复杂度 $O(n \log n)$，对 $n \le 3\times10^5$ 可行

---

8. 示例验证（简略）

以题目示例 0010010011 为例，标程输出 $12$，与题目给出的子串列表一致。

---

总结

这道题的核心是：

1. 通过巧妙的权重分配（$0 \to +1$，$1 \to -3$）将游戏结果转化为前缀和比较
2. 发现胜负条件与子串长度模 $4$ 有关
3. 使用 $4$ 个树状数组按 $i \bmod 4$ 分类统计，快速计算所有合法子串

这种将博弈问题转化为前缀和统计的技巧，在处理环形或相邻删除类游戏时非常有效。