配点 : 100 点
問題文
整数 N,K 和长度 Q 整数序列 给出 D = (D_1, D_2, \dots, D_Q) 。 对于
(1, 2, \dots, N) 的排列 给出了 P = (P_1, P_2, \dots, P_N) ,顶点 1 到顶点 N 最多 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 关于,满足以下所有条件 (1, 2, \dots, N) 的排列 给出了 P 全体集合 \mathcal{S}_d 。
- 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 的最长递增子序列的长度。
制約
- 所有输入均为整数
- 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
部分点
- 附加限制 如果正确答案是满足 N \le 500 的数据集 给出 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N K Q D_1 D_2 \vdots D_Q
出力
q = 1, 2, \dots, Q 请按顺序以换行分隔输出对应的答案。
入力例 1
4 0 3 1 2 3
出力例 1
0 2 2
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
2 100 1 1
出力例 2
1
入力例 3
314159 26535 5 271 828 1828 45904 52353
出力例 3
765557189 351184939 258247317 305813889 68486796