---

题目 F1. 破城者计数（简单版）

---

第一部分：原题 D1B 的分析

1.1 问题重述

有 $n$ 个城市排成一行，编号 $1, 2, \dots, n$。
从某个起始城市开始，时刻 $1$ 征服它。
此后每个时刻，征服一个与已征服区域相邻的城市。
城市 $i$ 必须在时刻 $\le a_i$ 之前被征服。
问：有多少个起始城市可以获胜？

---

1.2 关键引理

引理 1（必胜策略）
对于固定的起始城市，如果存在获胜策略，则以下策略 1 一定可行：

如果存在右侧城市，其距离当前已征服区间右端点的距离为 $t$，且它的截止时间恰好是 $t$（即它必须在 $t$ 步内被征服），那么下一步就向右扩展。否则向左扩展。

证明：

• 所有右侧城市的限制会自然满足（因为向右移动时，右侧城市的剩余时间恰好等于距离）。
• 这种策略最小化了到达左侧任何城市的时间，因此如果任何策略可行，这个策略也可行。

推论（策略 2）
如果存在某个方向上的城市，其距离为 $t$，且截止时间为 $t$，则向该方向扩展。否则任意方向均可。

---

1.3 可行起始城市的区间结构

引理 2
可行起始城市要么为 $0$ 个，要么恰好是区间

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

证明：

• 若 $x < l$，则存在某个 $i$ 使得 $i - a_i + 1 > x$，意味着城市 $i$ 无法在截止时间前从 $x$ 到达。
• 若 $x > r$，类似。
• 若 $x \in [l, r]$，使用策略 2 可以先征服 $I$ 内所有城市（因为它们彼此距离 $\le a_i$ 限制），再征服外部城市，从而获胜。
• 因此 $I$ 内城市要么全部可行，要么全部不可行。但由构造可知全部可行，故 $I$ 就是可行起始城市集。

推论
区间 $I = [l, r]$ 给出了 $a_i$ 的下界：

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

此外，使用策略 1 时，第一次向右移动的时刻决定了 $l$。

---

第二部分：计数问题的动态规划

我们要统计数组 $a_1, \dots, a_n$（$1 \le a_i \le n$）的数量，使得 D1B 的答案（可行起始城市数）恰好为 $k$。

---

2.1 $O(n^4)$ 做法

步骤 1：枚举区间 $I = [l, r]$

设 $m = r - l + 1$。
对于 $i \in I$，下界为 $a_i \ge \max(i-l+1, r-i+1)$。
对于 $i \notin I$，下界为 $1$。

步骤 2：定义 DP 状态

使用策略 1（确定性顺序）。
定义 $dp[i][j][k]$ 表示：

• 当前已征服区间为 $[i, j]$，
• $k$ 表示下一步是否被迫向右：
  • $k = 1$：必须向右（因为左侧某城市已到截止时间）
  • $k = 0$：可以向左或任意

步骤 3：转移

1. 向左扩展：从 $[i+1, j]$ 扩展到 $[i, j]$
   此时 $a_i$ 必须满足：

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

   并且 $k$ 必须为 $0$（因为向左扩展时不能被迫向右）。

2. 向右扩展：从 $[i, j-1]$ 扩展到 $[i, j]$
   如果希望新状态 $k=0$，必须 $a_j = j-i+1$（即 $j$ 是迫使向右的临界点）。
   如果希望新状态 $k=1$，则 $a_j \ge j-i+1$ 且不是临界点。

步骤 4：计算 int_ans[l][r]

int_ans[l][r] 表示区间 $[l, r]$ 为 $I$ 时，满足下界且使用策略 1 的 $(a, \text{访问顺序})$ 对数。
初始状态 $dp[l][l][0] = 1$，最终答案 int_ans[l][r] = dp[l][r][0]。

---

2.2 修正为恰好区间 $I$

对于固定 $a$，访问顺序仅取决于起始城市，且每个起始城市对应一个顺序。
因此，区间 $[l, r]$ 对应的数组 $a$ 的数量为：

$$\frac{\text{int\_ans}[l][r]}{r-l+1}$$

为了得到 $I$ 恰好是可行起始城市集（而不是包含更大的区间），使用二维容斥：

$$\text{ans}[l][r] = \frac{\text{int\_ans}[l][r]}{m} - \frac{\text{int\_ans}[l-1][r]}{m+1} - \frac{\text{int\_ans}[l][r+1]}{m+1} + \frac{\text{int\_ans}[l-1][r+1]}{m+2} $$

其中 $m = r-l+1$，且当 $l=1$ 或 $r=n$ 时边界项为 $0$。

---

2.3 处理 $k=0$ 的情况

所有数组总数为 $n^n$。
对于 $k \ge 1$，答案已由上述方法得到。
因此：

$$\text{answer}[0] = n^n - \sum_{k=1}^n \text{answer}[k] $$

---

第三部分：优化到 $O(n^3)$ 和 $O(n^2)$

3.1 $O(n^3)$ 优化思路

注意到对于固定 $k = r-l+1$，所有长度为 $k$ 的区间 $[l, r]$ 的下界函数形式相似，只是平移。
可以在长度为 $2n$ 的数组上运行一次 DP，然后提取所有长度为 $n$ 的子区间结果。

具体地，构造一个长度为 $2n$ 的数组，令 $a_i$ 的下界为：

$$b_i = \max(i - (n-k+1) + 1,\; n - i + 1) \quad \text{(调整后)} $$

然后在 $[1, 2n]$ 上跑 DP，结果 dp[i][i+n-1][0] 就对应原问题中某个 $k$ 的答案。

---

3.2 $O(n^2)$ 终极优化

关键观察：可以分别处理 $l$ 和 $r$ 的限制。

反向 DP：从时刻 $n$ 倒推到时刻 $1$。

• 在反向过程中，$l$ 和 $r$ 的影响可以解耦。
• 先忽略 $l$ 的限制（只考虑 $r$），此时转移非常简单（总是向左扩展）。
• 然后利用引理 2 的推论确定 $l$，并修正结果。

这样状态数降为 $O(n^2)$，总复杂度 $O(n^2)$。

---

第四部分：最终答案格式

对于每个测试用例，输出 $n+1$ 个整数：第 $i$ 个整数对应 $k = i-1$ 时的数组个数（模 $p$）。

---

第五部分：示例验证

以 $n=2$ 为例：

• $k=0$：$[1,1]$ → 1 个
• $k=1$：$[1,2], [2,1]$ → 2 个
• $k=2$：$[2,2]$ → 1 个

输出：1 2 1 ✅

---

这样，我们就得到了从 $O(n^4)$ 到 $O(n^2)$ 的完整解法推导。