---

题目重述

有 $n$ 个城市排成一行，编号 $1,2,\dots,n$。
在时刻 $1$ 征服一个起始城市，之后每个时刻必须征服一个与已征服区域相邻的城市。
对每个城市 $i$，必须在其截止时间 $a_i$ 之前（含 $a_i$）征服它。
$a_i$ 是 $1$ 到 $n$ 之间的整数。

对于给定的数组 $a$，定义“好的起始城市”为：存在一种征服顺序（策略）满足所有 $a_i$ 约束。
要求：对每个 $k=0,1,\dots,n$，计算有多少个数组 $a$ 使得好的起始城市个数恰好为 $k$。
答案对给定质数 $p$ 取模。

---

关键结论（Lemma）

Lemma 1

对于固定起始城市，若存在获胜策略，则以下贪心策略必胜：

• 如果存在某个右侧城市，其距离为 $t$ 且截止时间恰好为 $t$（即 $a_j = \text{距离}$），则向右走；
• 否则向左走。

推论：若存在获胜策略，则以下双向贪心也必胜：

• 若某方向存在 $a_j = \text{距离}$ 的城市，则往该方向走；
• 否则任意方向。

Lemma 2

好的起始城市集合要么为空，要么是一个连续区间

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

且 $l \le r$ 时区间非空，此时区间内所有城市都是好的起始城市。

证明思路：

• 若 $x < l$，则存在某个 $i$ 使得 $i-a_i+1 > x$，即 $i$ 距离 $x$ 超过 $a_i-1$，不可达。
• 若 $x \in [l,r]$，用双向贪心先征服 $I$ 内所有城市（时间 $\le r-l+1$），再征服外部，不违反截止时间。

因此，好的起始城市个数 = $r-l+1$。

---

从区间 $[l,r]$ 到数组 $a$ 的约束

由 $I = [l,r]$ 可得：

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

因为 $i$ 到 $l$ 的距离为 $i-l+1$，到 $r$ 的距离为 $r-i+1$，必须在这两个时间内征服 $i$。

另外，在贪心策略 1 下，访问顺序完全确定：

• 若 $a_j = j-l+1$ 且 $j$ 是当前区间右端，则必须向右扩展；
• 否则向左扩展。

这个贪心会产生唯一的访问顺序（对固定 $l,r$ 和固定起始点）。

---

动态规划设计（标程思路）

状态定义

设 $dp[i][j][0/1]$ 表示：
当前已征服的区间是 $[i,j]$，
$k=0$ 表示上一步是从 $i$ 向左扩展来的（当前准备向右扩展），
$k=1$ 表示上一步是从 $j$ 向右扩展来的（当前准备向左扩展）。

但标程更常用的是 $f[i][j]$ 表示区间 $[i,j]$ 作为 $I$ 时的方案数。

---

转移

情况 1：从 $[i+1,j]$ 扩展到 $[i,j]$
这要求 $a_i \ge j-i+1$（因为 $i$ 在时刻 $j-i+1$ 被征服）
还要满足 $a_i \ge i-l+1$ 和 $a_i \ge r-i+1$，但 $l,r$ 固定，所以是：

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

并且此步只能是向左扩展，所以前一步 $dp[i+1][j]$ 的 $k$ 必须为 $1$（或标程里用方向标识）。

情况 2：从 $[i,j-1]$ 扩展到 $[i,j]$
要求 $a_j = j-i+1$（否则贪心不会向右扩展）
并且 $a_j$ 必须 $\ge j-l+1$ 和 $\ge r-j+1$，所以：

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

这个不等式自动满足当 $[l,r]$ 含 $j$ 且 $j-i+1$ 足够大。

---

初始状态

区间长度为 1 时，$dp[i][i] = 1$（只有一种访问顺序）。

---

统计恰好 $k$ 个好的起始城市

第一步：统计 $I=[l,r]$ 为好的起始城市集合的方案数

设 $ans[l][r]$ 表示 $I=[l,r]$ 时的数组个数（此时好的起始城市个数为 $r-l+1$）。

由 DP 可算出 $ans[l][r]$。

第二步：容斥得到“恰好 $I=[l,r]$”

若 $[l,r]$ 是好的起始城市集合，则必须 $[l,r]$ 为满足约束的最大区间。
即：

• 不能有 $l-1$ 也是好的起始城市（否则 $I$ 更大）
• 不能有 $r+1$ 也是好的起始城市

这等价于：

$$a_{l-1} < (l-1)-l+1 = 0$$

不可能，所以 $l$ 必须是 $\min I$ 自然满足。

更精确的容斥：

$$\text{exact}[l][r] = ans[l][r] - ans[l-1][r] - ans[l][r+1] + ans[l-1][r+1] $$

其中 $ans[l][r]$ 表示 $[l,r]$ 是好的起始城市集合的子集的方案数（即所有 $[l',r'] \supseteq [l,r]$ 的方案数）。

由 DP 可直接得到 $ans[l][r]$。

---

复杂度优化

直接对每个 $[l,r]$ 做 DP 是 $O(n^4)$。
标程优化到 $O(n^2)$：

• 固定 $r$，动态处理 $l$
• 注意到 $a_i \ge i-l+1$ 和 $a_i \ge r-i+1$ 在 $l$ 变化时只有 $i-l+1$ 变化
• 用前缀和或差分来快速更新 DP 状态
• 最终 $O(n^2)$ 求出所有 $ans[l][r]$

---

答案输出

• 对 $k \ge 1$，答案 $= \sum_{r-l+1 = k} \text{exact}[l][r]$
• 对 $k = 0$，答案 $= n^n - \sum_{k \ge 1} \text{ans}_k$

模 $p$ 计算即可。

---

示例验证（n=3）

已知输出：

k=0: 14
k=1: 7
k=2: 4
k=3: 2

检查：

• $k=3$ 对应 $I=[1,3]$，$a_i \ge i$，只有 $[3,2,3],[3,3,3]$ 等，共 2 个 ✓
• $k=2$ 对应 $I=[1,2]$ 或 $[2,3]$，分别统计 ✓

---

总结核心公式

1. 好起始城市集合 = 连续区间 $[l,r]$
2. 约束：$a_i \ge \max(i-l+1,\; r-i+1)$
3. 贪心访问顺序唯一确定
4. DP 状态：$dp[i][j]$ 表示区间 $[i,j]$ 被征服的方案数
5. 转移：向左或向右扩展，注意截止时间必须恰好等于扩展步数（向右时）
6. 容斥：$exact[l][r] = dp[l][r] - dp[l-1][r] - dp[l][r+1] + dp[l-1][r+1]$
7. 复杂度：$O(n^2)$

这样即可在 $O(n^2)$ 内求解所有 $k$ 的答案。