CF2119D.Token Removing

r-906 & 初音未来 - All I Can See Is You

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

定义一个长度为 $n$ 的合法序列 $a$ 的权值 $f(a)$ 如下：

• 初始时，在数轴的闭区间 $[1, n]$ 上的每个整数点各放置一个标记。
• 依次进行 $n$ 次操作。在第 $i$ 次操作时，如果 $a_i \ne 0$，则从闭区间 $[a_i, i]$ 内尚未被移除的标记中移除一个；否则，不进行任何操作。
• $f(a)$ 表示移除标记的方案数。如果存在某个 $t$，使得两种方案在第 $t$ 次操作时移除的标记位置不同，则认为这两种方案不同。

例如，$f([0, 2, 1]) = 2$，因为可以依次移除 $2, 1$ 或 $2, 3$ 位置的标记。

JT 给你两个整数 $n, m$，请你求出所有长度为 $n$ 的合法序列的权值之和，即所有 $(n + 1)!$ 个合法序列的 $f(a)$ 之和。由于答案可能过大，请输出其对 $m$ 取模的结果。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来每组测试用例一行，包含两个整数 $n$ 和 $m$（$1 \le n \le 5000, 10^8 \le m \le 1.01 \cdot 10^9$），分别表示合法序列的长度和取模的数。

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

对于每个测试用例，输出一个整数，表示所有 $(n + 1)!$ 个长度为 $n$ 的合法序列的权值之和，对 $m$ 取模后的结果。

在第一个测试用例中，合法序列为 $[0]$ 和 $[1]$，答案为 $f([0]) + f([1]) = 1 + 1 = 2$。

在第二个测试用例中，合法序列为 $[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]$。其中 $[0, 1]$ 的权值为 $2$，其余均为 $1$，所以答案为 $5 \times 1 + 1 \times 2 = 7$。

由 ChatGPT 4.1 翻译