题解：F2. 破速者计数（中等版）

---

提示 1

给定一个起始城市，你想获胜。找出几种获胜策略（如果可能），并尝试使用最简单的策略。

---

提示 2

可行的起始城市要么是 $0$ 个，要么是区间

$$I := \bigcap_{i=1}^{n} [i - a_i + 1,\ i + a_i - 1] = [l, r] $$

中的所有城市。

---

提示 3

由此可得 $a_i$ 的一些下界约束。

---

提示 4

固定区间 $I$，尝试设计一个（较慢的）动态规划。

---

提示 5

计数路径似乎比计数数组更容易。确保对于每个数组，你恰好构造出一条路径（或者容易处理的若干条路径）。

---

提示 6

在你的 DP 中，需要计算多少个不同的状态？

---

引理 1

对于固定的起始城市，如果能够获胜，则以下策略有效：

策略 1：如果存在右侧的城市，其距离为 $t$ 且截止时间为 $t$ 步，则向右走；否则向左走。

证明：

• 所有右侧的约束都能满足。
• 该策略最小化到达左侧任何城市的时间。因此，如果任何策略可行，该策略也可行。

---

推论

对于固定的起始城市，如果能够获胜，则以下策略也有效：

策略 2：如果存在某个城市，其距离为 $t$ 且截止时间为 $t$ 步，则向该方向走；否则任意方向。

---

引理 2

可行的起始城市要么是 $0$ 个，要么是区间

$$I := \bigcap_{i=1}^{n} [i - a_i + 1,\ i + a_i - 1] = [l, r] $$

中的所有城市。

证明：

• $I$ 外的城市必败，因为存在至少一个无法到达的城市。
• 从 $I$ 中任意城市 $x$ 出发，使用策略 2。
• 可以证明：对于任意 $x \in I$，策略 2 能先访问 $I$ 中的所有城市，然后再访问其余城市。
• 因此 $I$ 中的城市要么全胜，要么全败。
• 区间 $I$ 给出了 $a_i$ 的下界：$a_i \ge \max(i - l + 1,\ r - i + 1)$。
• 可以验证，先访问区间 $I$ 不会违反策略 2。

---

推论

如果使用策略 1，第一次向右移动就决定了 $l$。

---

$O(n^4)$ DP

枚举非空区间 $I = [l, r]$。计算下界：

$$a_i \ge \max(i - l + 1,\ r - i + 1)$$

注意：策略 1 是确定性的（对于固定的 $(起始城市,\ a)$，给出唯一的访问顺序）。接下来我们使用策略 1。

定义：

$$dp[i][j][k] = \text{限制在区间 }[i,j]\text{ 上的 }(a,\ 访问顺序)\text{ 对数} $$

其中 $k$ 表示“下一步是否被迫向右走”（$k \in \{0,1\}$）。

转移：

1. 从 $[i+1,j]$ 扩展到 $[i,j]$：

   • 必须满足 $a_i \ge \max(i-l+1,\ r-i+1,\ j-i+1)$（因为它在时间 $j-i+1$ 被访问）
   • 此时 $k$ 必须为 $0$

2. 从 $[i,j-1]$ 扩展到 $[i,j]$，且希望 $k=0$：

   • 必须满足 $a_j = j-i+1$（意味着 $j$ 是迫使你向右走的那个城市）

在代码中，结果存储在 int_ans[i][j] 中。

---

处理“恰好是唯一可行起始城市”

我们想要统计使得 $I = [l,r]$ 中的城市是唯一可行起始城市的 $(a,\ 访问顺序)$ 对数。

这类似于二维前缀和：

$$\text{int\_ans}[i][j] \ -= \text{int\_ans}[i-1][j] + \text{int\_ans}[i][j+1] - \text{int\_ans}[i-1][j+1] $$

对于固定的 $a$，访问顺序只取决于起始城市，因此区间 $[i,j]$ 对应的数组个数为：

$$\frac{\text{int\_ans}[i][j]}{j-i+1}$$

这样就解决了 $k \ge 1$ 的情况。$k=0$ 的答案就是 $n^n$ 减去所有其他答案。

---

$O(n^3)$ DP

在上一节中，我们对 $O(n^2)$ 个不同的“下界数组”运行了相同的 DP。现在我们要用一次 DP 解决一个固定的 $k$。

对于固定的 $k$，注意到：如果在长度为 $2n$ 的数组上运行 DP，从 $I = [n-k+1, n]$ 得到的下界数组包含了所有需要的长度为 $n$ 的子数组作为下界。

因此可以一次 DP 得到所有结果：

$$\text{答案}[k] = dp[n-k+1][n-k+1+n-1][0]$$

---

$O(n^2)$ DP

我们仍然有 $O(n^3)$ 个不同的状态。如何简化“下界数组”？

关键观察：可以分别处理 $l$ 和 $r$！

只基于 $r$ 创建下界数组（得到 $O(n^2)$ 个不同状态），然后利用引理 2 的推论找到 $l$。

在找到 $l$ 之前的转移非常简单（总是向左走）。

一种实现 $O(n^2)$ 复杂度的方法是：逆向处理策略 1 和 DP（从时间 $n$ 到时间 $1$）。

---

最终复杂度

$$O(n^2)$$

---

算法总结

1. 对于每个 $k$ 从 $1$ 到 $n$，计算长度为 $n$ 且恰好有 $k$ 个可行起始城市的数组个数
2. 使用逆向 DP，状态数为 $O(n^2)$
3. $k=0$ 的答案由总数 $n^n$ 减去其他答案得到
4. 所有结果对素数 $p$ 取模

---

关键公式汇总

• 可行起始城市区间：$I = \bigcap_{i=1}^{n} [i-a_i+1,\ i+a_i-1]$
• 下界约束：$a_i \ge \max(i-l+1,\ r-i+1)$
• 访问时间：城市 $i$ 在区间 $[l,r]$ 中被访问的时间为 $\max(i-l+1,\ r-i+1)$
• 数组总数：$n^n$
• 答案对 $p$ 取模，$p$ 为素数