Game of AI (hard version)

题目描述

This is the hard version of this problem. The difference between easy and hard versions is the constraint on $ k $ and the time limit. Notice that you need to calculate the answer for all positive integers $ n \in [1,k] $ in this version. You can make hacks only if both versions of the problem are solved. Cirno is playing a war simulator game with $ n $ towers (numbered from $ 1 $ to $ n $ ) and $ n $ bots (numbered from $ 1 $ to $ n $ ). The $ i $ -th tower is initially occupied by the $ i $ -th bot for $ 1 \le i \le n $ . Before the game, Cirno first chooses a permutation $ p = [p_1, p_2, \ldots, p_n] $ of length $ n $ (A permutation of length $ n $ is an array of length $ n $ where each integer between $ 1 $ and $ n $ appears exactly once). After that, she can choose a sequence $ a = [a_1, a_2, \ldots, a_n] $ ( $ 1 \le a_i \le n $ and $ a_i \ne i $ for all $ 1 \le i \le n $ ). The game has $ n $ rounds of attacks. In the $ i $ -th round, if the $ p_i $ -th bot is still in the game, it will begin its attack, and as the result the $ a_{p_i} $ -th tower becomes occupied by the $ p_i $ -th bot; the bot that previously occupied the $ a_{p_i} $ -th tower will no longer occupy it. If the $ p_i $ -th bot is not in the game, nothing will happen in this round. After each round, if a bot doesn't occupy any towers, it will be eliminated and leave the game. Please note that no tower can be occupied by more than one bot, but one bot can occupy more than one tower during the game. At the end of the game, Cirno will record the result as a sequence $ b = [b_1, b_2, \ldots, b_n] $ , where $ b_i $ is the number of the bot that occupies the $ i $ -th tower at the end of the game. However, as a mathematics master, she wants you to solve the following counting problem instead of playing games: Count the number of different pairs of sequences $ a $ , $ b $ from all possible choices of sequence $ a $ and permutation $ p $ . Calculate the answers for all $ n $ such that $ 1 \le n \le k $ . Since these numbers may be large, output them modulo $ M $ .

输入输出格式

输入格式

The only line contains two positive integers $ k $ and $ M $ ( $ 1\le k\le 10^5 $ , $ 2\le M\le 10^9 $ ). It is guaranteed that $ 2^{18} $ is a divisor of $ M-1 $ and $ M $ is a prime number.

输出格式

Output $ k $ lines, where the $ i $ -th line contains a non-negative integer, which is the answer for $ n=i $ modulo $ M $ .

输入输出样例

输入样例 #1

8 998244353

输出样例 #1

0
2
24
360
6800
153150
4057452
123391016

说明

For $ n=1 $ , no valid sequence $ a $ exists. We regard the answer as $ 0 $ . For $ n=2 $ , there is only one possible array $ a $ : $ [2, 1] $ . - For array $ a $ is $ [2, 1] $ and permutation $ p $ is $ [1, 2] $ , the sequence $ b $ will be $ [1, 1] $ after all rounds have finished. The details for each rounds: - In the first round, the first bot will begin its attack and successfully capture the tower $ 2 $ . After this round, the second bot will be eliminated and leave the game as all of its towers are occupied by other bots. - In the second round, the second bot is not in the game. - For array $ a $ is $ [2, 1] $ and permutation $ p $ is $ [2, 1] $ , the sequence $ b $ will be $ [2, 2] $ after all rounds have finished. The details for each rounds: - In the first round, the second bot will begin its attack and successfully capture the tower $ 1 $ . After this round, the first bot will be eliminated and leave the game as all of its towers are occupied by other bots. - In the second round, the first bot is not in the game. So the number of different pairs of sequences $ (a,b) $ is $ 2 $ ( $ [2, 1] $ , $ [1, 1] $ and $ [2, 1] $ , $ [2, 2] $ ) for $ n=2 $ .

**AI游戏（困难版本）**

**题目描述：**
这是这个问题的困难版本。简单和困难版本之间的区别在于对 $ k $ 的限制和时间限制。注意，在这个版本中，你需要计算所有正整数 $ n \in [1,k] $ 的答案。只有当两个版本的问题都解决时，你才能进行hack。

Cirno正在玩一个战争模拟器游戏，游戏中有 $ n $ 座塔（编号从 $ 1 $ 到 $ n $）和 $ n $ 个机器人（编号从 $ 1 $ 到 $ n $）。第 $ i $ 座塔最初由第 $ i $ 个机器人占据，对于 $ 1 \le i \le n $。

在游戏开始之前，Cirno首先选择一个长度为 $ 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 $ 且对所有 $ 1 \le i \le n $，有 $ a_i \ne i $）。

游戏有 $ n $ 轮攻击。在第 $ i $ 轮中，如果第 $ p_i $ 个机器人仍在游戏中，它将开始攻击，结果是第 $ a_{p_i} $ 座塔被第 $ p_i $ 个机器人占据；之前占据第 $ 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,**AI游戏（困难版本）** **题目描述：** 这是这个问题的困难版本。简单和困难版本之间的区别在于对 $ k $ 的限制和时间限制。注意，在这个版本中，你需要计算所有正整数 $ n \in [1,k] $ 的答案。只有当两个版本的问题都解决时，你才能进行hack。 Cirno正在玩一个战争模拟器游戏，游戏中有 $ n $ 座塔（编号从 $ 1 $ 到 $ n $）和 $ n $ 个机器人（编号从 $ 1 $ 到 $ n $）。第 $ i $ 座塔最初由第 $ i $ 个机器人占据，对于 $ 1 \le i \le n $。 在游戏开始之前，Cirno首先选择一个长度为 $ 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 $ 且对所有 $ 1 \le i \le n $，有 $ a_i \ne i $）。 游戏有 $ n $ 轮攻击。在第 $ i $ 轮中，如果第 $ p_i $ 个机器人仍在游戏中，它将开始攻击，结果是第 $ a_{p_i} $ 座塔被第 $ p_i $ 个机器人占据；之前占据第 $ 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,