D. Token Removing

问题描述

定义一个整数序列 $a$ 是有效的，当且仅当对于所有 $1 ≤ i ≤ n$，都有 $0 ≤ a_i ≤ i$。

定义一个长度为 $n$ 的有效序列 $a$ 的权重 $f(a)$：

• 最初，在数轴上的闭区间 $[1, n]$ 的每个整数点上放置一个令牌。
• 按顺序执行 $n$ 次操作。在第 $i$ 次操作期间，如果 $a_i \neq 0$，则在闭区间 $[a_i, i]$ 中移除一个尚未被移除的令牌；否则，不执行任何操作。
• $f(a)$ 是移除令牌的方法数。如果存在一个 $t$，使得两种方式在第 $t$ 次操作中移除的令牌位置不同，则认为这两种方式是不同的。
• 例如，$f([0,2,1]) = 2$，因为我们可以按顺序移除位置在 $2,1$ 或 $2,3$ 的令牌。

JT 给你两个整数 $n, m$，并要求你找出所有 $(n+1)!$ 个长度为 $n$ 的有效序列的权重之和。由于答案可能太大，请将其对 $m$ 取模后输出。

输入

每个测试包含多个测试用例。第一行是测试用例的数量 $t$ ($1 ≤ t ≤ 1000$)。接下来是测试用例的描述。

每个测试用例的唯一一行包含两个整数 $n$ 和 $m$ ($1 ≤ n ≤ 5000$, $10^8 ≤ m ≤ 1.01 × 10^9$) — 有效序列的长度和模数。

保证所有测试用例的 $n^2$ 的总和不超过 $2.5 × 10^7$。

输出

对于每个测试用例，输出一个整数 — 所有 $(n+1)!$ 个长度为 $n$ 的有效序列的权重之和，对 $m$ 取模。

题解

目标是计算所有可能的有效序列 a 的权重 f(a) 之和，对 m 取模。权重 f(a) 是基于序列 a 移除令牌的方法数。

1. 核心思想：转换视角

解决方案没有遍历每个可能的序列 a 并计算其贡献，而是将问题反过来思考。我们提出了一个不同的问题：

对于一个特定的被移除的令牌位置集合 P，它对最终答案的总贡献是多少？

如果我们能为任何给定的集合 P 计算出这个值，那么我们就可以将这些贡献在所有可能的集合 P 上求和，从而得到最终答案。

2. 单个令牌集合 P 的贡献

假设我们决定移除一个位于位置 $P = {p_0, p_1, ..., p_{k-1}}$ 的特定 $k$ 个令牌集合。为方便起见，我们按降序对它们进行排序：$n ≥ p_0 > p_1 > ... > p_{k-1} ≥ 1$。

要移除这个集合 P，我们需要找到一个序列 $a$ 和一个相应的移除计划。这涉及两个主要部分：

2.1 选择 $a[t]$ 的值

对于在某个步骤 $t_j$ 被移除的每个令牌 $p_j$，条件是 $a[t_j] ≤ p_j ≤ t_j$。值 $a[t_j]$ 可以是 1 到 $p_j$ 之间的任何整数。这为 $a[t_j]$ 提供了 $p_j$ 种选择。对于所有 $k$ 个令牌，a 值的总选择数是乘积 $p_0 × p_1 × ... × p_{k-1}$。

2.2 分配移除步骤 $t_j$

我们需要为每个令牌 $p_j$ 分配一个唯一的移除步骤 $t_j$，使得 $t_j ≥ p_j$。

• 对于最大的令牌 $p_0$，它可以在从 $p_0$ 到 $n$ 的任何步骤中被移除。有 $n - p_0 + 1$ 个可用步骤。
• 对于第二大的令牌 $p_1$，它可以在从 $p_1$ 到 $n$ 的任何步骤中被移除，除了已经被 $p_0$ 占用的步骤。由于 $p_0 > p_1$，$p_0$ 的步骤对于 $p_1$ 来说总是一个有效（但不可用）的步骤。这留下了 $(n - p_1 + 1) - 1$ 种选择。
• 推广来说，对于令牌 $p_j$（它是第 $j$ 大的，其中 $j$ 从 0 开始），有 $n - p_j + 1$ 个潜在步骤。然而，其中 $j$ 个步骤已经被分配给了比 $p_j$ 大的 $j$ 个令牌。这为 $t_j$ 留下了 $(n - p_j + 1 - j)$ 种选择。

2.3 最终贡献公式

结合这两个部分，单个固定集合 P 的总贡献是：

我们的新目标是计算这个值在所有可能的非空子集 $P \subseteq \{1, 2, ..., n\}$ 上的和。

3. 动态规划解法

枚举所有 $2^n$ 个子集 P 太慢了。我们可以使用动态规划来高效地计算这个和。关键是逐个元素地构建集合 P。

关键的洞察是按降序考虑元素，从 $n$ 到 $1$。

3.1 DP 状态定义

让我们定义我们的 DP 状态：

$\text{dp}[i][k]$ = 所有大小为 $k$ 的集合 $P$ 的贡献之和，其中所有选择的令牌都来自范围 ${i, i+1, ..., n}$。

3.2 DP 转移

我们通过从 $n$ 向下迭代到 $1$ 来计算这个值。对于每个 $i$，我们做出一个决定：

1. 不将 $i$ 包含在我们的集合 P 中：如果我们不选择 $i$，我们仍然必须选择 $k$ 个令牌，但现在它们都必须来自范围 ${i+1, ..., n}$。这种情况的贡献之和根据定义是 $\text{dp}[i+1][k]$。

2. 将 $i$ 包含在我们的集合 P 中：如果我们选择 $i$，我们需要从范围 ${i+1, ..., n}$ 中选择另外 $k-1$ 个令牌。

   • 来自 ${i+1, ..., n}$ 的所有此类 $k-1$ 个令牌集合的贡献之和是 $\text{dp}[i+1][k-1]$。
   • 现在，我们将 $i$ 添加到这些集合中的每一个。由于 $i$ 小于 ${i+1, ..., n}$ 中的任何数，它将始终是新的 $k$ 元素集合中最小的元素。这意味着它的排名（从大到小，0-索引）将始终是 $k-1$。
   • 因此，$i$ 的乘法因子是 $i × (n - i + 1 - (k-1))$。
   • 这种情况的总贡献是 $\text{dp}[i+1][k-1] × i × (n - i + 2 - k)$。

3.3 DP 递推关系

结合这些情况，我们得到递推关系：

基本情况:

• $\text{dp}[n+1][0] = 1$ (表示选择空集的一种方式)
• $\text{dp}[n+1][k] = 0$ for $k > 0$

最终答案: 最终答案是所有可能的集合大小 $k$ 的贡献之和，考虑从 1 到 $n$ 的所有数字。即 $\sum_{k=0}^{n} \text{dp}[1][k]$。

提交链接