← 返回题目列表

AtCoder · utpc2025_i

I. 反演图

中文机器翻译题面 查看原题

配点 : 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