← 返回题目列表

Codeforces · 2119/D

D. 令牌删除

中文机器翻译题面 查看原题
r-906 & 初音未来 - 我所看到的就是你

定义整数序列 $$$a$$$ 有效 当且仅当 $$$\forall 1 \le i \le n, 0 \le a_i \le i$$$。

定义 重量 $$$f(a)$$$ 的 有效 序列 $$$a$$$,长度为 $$$n$$$:

  • 最初,在数轴上闭合线段 $$$[1, n]$$$ 中的每个整数点放置一个标记。
  • 按顺序执行 $$$n$$$ 操作。在第 $$$i$$$ 次操作过程中,如果 $$$a_i \ne 0$$$,则移除闭合段 $$$[a_i, i]$$$ 中尚未移除的 token;否则,什么也不做。
  • $$$f(a)$$$ 是删除标记的方法数量。如果存在$$$t$$$,使得在第$$$t$$$操作中这两种方式删除的标记的位置不同,则认为两种方式是不同的。

例如,$$$f([0, 2, 1]) = 2$$$,因为我们可以依次删除$$$2, 1$$$ 或$$$2, 3$$$ 上的标记。

JT 给你两个整数 $$$n, m$$$ 并要求你求它们的总和 重量全部$$$(n + 1)!$$$ 有效 长度为 $$$n$$$ 的序列。由于答案可能太大,请打印它对 $$$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$$$ 为模。

示例

输入
复制

6
1 1000000007
2 1000000007
3 1000000007
4 1000000007
5 1000000007
114 514191981

输出
复制

2
7
37
273
2672
393775292

注意

在第一个测试用例中, 有效 序列是$$$[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 \cdot 1 + 1 \cdot 2 = 7$$$。