AT_arc174_e.[ARC174E] Existence Counting

给定整数 $N,K$。现在考虑所有满足以下条件的长度为 $K$ 的数列 $a=(a_1,a_2,\dots,a_K)$：

• $a_i$ 是满足 $1 \le a_i \le N$ 的整数；
• $a$ 的所有元素互不相同。

将所有可能的数列 $a$ 按照字典序排列，得到一个“数列的集合” $s$。

现在给定集合 $s$ 中的一个数列 $P$，对于每个整数 $t=1,2,\dots,N$，请回答以下问题：

• 满足下列所有条件的数列 $b$ 的个数，模 $998244353$ 后的结果是多少？
  • 数列 $b$ 存在于集合 $s$ 中；
  • 数列 $b$ 中包含整数 $t$；
  • 数列 $b$ 的字典序不大于数列 $P$。

关于数列的字典序：数列 $A=(A_1,\ldots,A_{|A|})$ 的字典序严格小于数列 $B=(B_1,\ldots,B_{|B|})$，当且仅当满足以下两条之一：

1. $|A| < |B|$ 且 $(A_1,\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$；
2. 存在整数 $1 \leq i \leq \min\{|A|,|B|\}$，使得
   • $(A_1,\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$；
   • $A_i < B_i$。

输入通过标准输入给出，格式如下：

$N$ $K$ $P_1$ $P_2$ $\dots$ $P_K$

共输出 $N$ 行。
第 $i$ 行输出当 $t=i$ 时问题的答案。

限制条件

• 输入均为整数。
• $1 \le K \le N \le 3 \times 10^5$。
• $P$ 满足题目中的条件。

样例解释 1

在本样例中，$N=4,K=2$。此时，集合 $s=((1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3))$。在集合 $s$ 中，且字典序不大于 $(3,2)$ 的数列中：

• 包含 $1$ 的有 $(1,2),(1,3),(1,4),(2,1),(3,1)$ 共 $5$ 个；
• 包含 $2$ 的有 $(1,2),(2,1),(2,3),(2,4),(3,2)$ 共 $5$ 个；
• 包含 $3$ 的有 $(1,3),(2,3),(3,1),(3,2)$ 共 $4$ 个；
• 包含 $4$ 的有 $(1,4),(2,4)$ 共 $2$ 个。

由 ChatGPT 4.1 翻译