← 返回题目列表

Codeforces · 1704/H2

H2. AI游戏(困难版)

中文机器翻译题面 查看原题

这是这个问题的困难版本。简单版和困难版的区别在于$$$k$$$ 的限制和时间限制。请注意,在此版本中,您需要计算 [1,k]$$$ 中所有正整数 $$$n \in 的答案。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

Cirno 正在玩一款战争模拟器游戏,其中有 $$$n$$$ 塔(编号从 $$$1$$$ 到 $$$n$$$)和 $$$n$$$ 机器人(编号从 $$$1$$$ 到 $$$n$$$)。第 $$$i$$$ 个塔最初被第 $$$i$$$ 个机器人占据 $$$1 \le i \le n$$$。

比赛前,琪露诺首先选择一个长度为$$$n$$$的排列$$$p = [p_1, p_2, \ldots, p_n]$$$(长度为$$$n$$$的排列是一个长度为$$$n$$$的数组,其中$$$1$$$和$$$n$$$之间的每个整数只出现一次)。之后,她可以选择一个序列 $$$a = [a_1, a_2, \ldots, a_n]$$$ ($$$1 \le a_i \le n$$$ 和 $$$a_i \ne i$$$ 对于所有 $$$1 \le i \le n$$$)。

游戏有 $$$n$$$ 轮攻击。在第 $$$i$$$-th 轮中,如果第 $$$p_i$$$-th 机器人仍在游戏中,它将开始攻击,结果 $$$a_{p_i}$$$-th 塔被第 $$$p_i$$$-th 机器人占领;之前占据第 $$$a_{p_i}$$$ 塔的机器人将不再占据它。如果第 $$$p_i$$$ 个机器人不在游戏中,则本轮不会发生任何事情。

每轮结束后,如果机器人没有占领任何塔,它将被淘汰并离开游戏。请注意,任何塔都不能被多于一个机器人占据,但在游戏过程中一个机器人可以占据多于一塔。

游戏结束时,Cirno 会将结果记录为序列 $$$b = [b_1, b_2, \ldots, b_n]$$$,其中 $$$b_i$$$ 是游戏结束时占领第 $$$i$$$ 塔的机器人编号。

然而,作为一名数学大师,她希望你解决以下计数问题,而不是玩游戏:

从序列 $$$a$$$ 和排列 $$$p$$$ 的所有可能选择中计算不同序列对 $$$a$$$、$$$b$$$ 的数量。

计算所有 $$$n$$$ 的答案,使得 $$$1 \le n \le k$$$。由于这些数字可能很大,因此输出它们对 $$$M$$$ 取模。

输入

唯一的一行包含两个正整数 $$$k$$$ 和 $$$M$$$ ($$$1\le k\le 10^5$$$, $$$2\le M\le 10^9$$$ )。保证 $$$2^{18}$$$ 是 $$$M-1$$$ 的约数,并且 $$$M$$$ 是素数。

输出

输出 $$$k$$$ 行,其中第 $$$i$$$ 行包含一个非负整数,这是 $$$n=i$$$ 模 $$$M$$$ 的答案。

示例

输入 #1

8 998244353

输出 #1

0
2
24
360
6800
153150
4057452
123391016

注意

对于 $$$n=1$$$,不存在有效序列 $$$a$$$。我们认为答案是$$$0$$$。

对于$$$n=2$$$,只有一个可能的数组$$$a$$$:$$$[2, 1]$$$。

- 对于数组 $$$a$$$ 为 $$$[2, 1]$$$ 且排列 $$$p$$$ 为 $$$[1, 2]$$$,在所有回合结束后序列 $$$b$$$ 将是 $$$[1, 1]$$$。每轮详细信息: 在第一轮中,第一个机器人将开始攻击并成功占领塔 $$$2$$$。本轮结束后,第二个机器人将被淘汰并离开游戏,因为它的所有塔都被其他机器人占据。 在第二轮中,第二个机器人不在游戏中。
- 对于数组 $$$a$$$ 为 $$$[2, 1]$$$ 且排列 $$$p$$$ 为 $$$[2, 1]$$$,在所有回合结束后,序列 $$$b$$$ 将是 $$$[2, 2]$$$。每轮详细信息: 在第一轮中,第二个机器人将开始攻击并成功占领塔 $$$1$$$。本轮结束后,第一个机器人将被淘汰并离开游戏,因为它的所有塔都被其他机器人占据。 在第二轮中,第一个机器人不在游戏中。

因此,$$$n=2$$$ 时,不同序列对 $$$(a,b)$$$ 的数量为 $$$2$$$ ($$$[2, 1]$$$, $$$[1, 1]$$$ 和 $$$[2, 1]$$$, $$$[2, 2]$$$)。