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 翻译