AT_utpc2025_i Inversion Graph

给定整数 $N,K$ 和长度为 $Q$ 的整数序列 $D = (D_1, D_2, \dots, D_Q)$。 对于 $(1, 2, \dots, N)$ 的一个排列 $P = (P_1, P_2, \dots, P_N)$，如下定义一个包含 $N$ 个顶点（顶点编号为 $1$ 到 $N$）的无向图 $G(P)$： > 对于所有满足 $1 \leq i < j \leq N$ 的整数对 $(i,j)$，当且仅当 $P_i > P_j$ 时，在 $G(P)$ 中顶点 $i$ 和顶点 $j$ 之间有一条边。 对于每个 $d = 1, 2, \dots, N-1$，设 $\mathcal{S}_d$ 为满足以下所有条件的所有 $(1,2,\dots,N)$ 的排列 $P$ 的集合： - $G(P)$ 是一棵树； - $G(P)$ 的直径为 $d$。 对于每个 $q = 1, 2, \dots, Q$，请计算 $\displaystyle \sum_{P \in \mathcal{S}_{D_q}} (\mathrm{LIS}(P))^K$ 模 $998244353$ 的值。其中，$\mathrm{LIS}(P)$ 表示排列 $P$ 的最长递增子序列的长度。

输入从标准输入按以下格式给出： > $N$ $K$ $Q$ $D_1$ $D_2$ $\vdots$ $D_Q$

请按顺序，每行输出一个答案，共 $Q$ 行。

### 部分分 - 若对满足额外限制 $N \le 500$ 的数据集作答正确，可获得 $10$ 分。 ### 样例解释 1 满足 $G(P)$ 是树的 $(1,2,3,4)$ 的排列 $P$ 共 $4$ 种： - $P = (2, 3, 4, 1)$：$G(P)$ 的直径为 $2$，$\mathrm{LIS}(P) = 3$。 - $P = (4, 1, 2, 3)$：$G(P)$ 的直径为 $2$，$\mathrm{LIS}(P) = 3$。 - $P = (2, 4, 1, 3)$：$G(P)$ 的直径为 $3$，$\mathrm{LIS}(P) = 2$。 - $P = (3, 1, 4, 2)$：$G(P)$ 的直径为 $3$，$\mathrm{LIS}(P) = 2$。 因此： - $q = 1$ 的答案为 $0$； - $q = 2$ 的答案为 $3^0 + 3^0 = 2$； - $q = 3$ 的答案为 $2^0 + 2^0 = 2$。 # 数据范围 - 所有输入均为整数 - $2 \leq N \leq 10^6$ - $0 \leq K \leq 10^{18}$ - $1 \le Q \le 2 \times 10^5$ - $1 \le D_1 < D_2 < \ldots < D_Q < N$ 由 ChatGPT 5 翻译