CF1704H2.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$.

这是本题的困难版本。简单版本与困难版本的区别在于对 $k$ 的限制以及时间限制。请注意，在本版本中，你需要对所有正整数 $n \in [1,k]$ 分别计算答案。仅当两个版本（简单版与困难版）均被成功 hack 时，才允许进行 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 i \le n$，均有 $1 \le a_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)$ 的总数。

对所有满足 $1 \le n \le k$ 的 $n$，分别计算答案。由于这些数值可能很大，请对给定模数 $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.

唯一一行包含两个正整数 $k$ 和 $M$（$1\le k\le 10^5$，$2\le M\le 10^9$）。保证 $2^{18}$ 是 $M-1$ 的约数，且 $M$ 是一个质数。

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

输出 $k$ 行，其中第 $i$ 行包含一个非负整数，即 $n=i$ 时的答案对 $M$ 取模的结果。

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$.

当 $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])$）。