#P18007. Inversion Graph
Inversion Graph
Inversion Graph
给定整数 及长度为 的严格递增整数序列 。
对于 的一个排列 ,定义无向图 :顶点为 ,对于 ,当且仅当 时,顶点 之间有一条边。
令 表示满足以下两个条件的所有排列 构成的集合:
- 是一棵树。
- 的直径为 。直径按路径上的边数计。
对每个询问 ,求
$$\sum_{P\in S_{D_q}}\operatorname{LIS}(P)^K\pmod{998244353},$$其中 是排列 的最长严格递增子序列长度。
输入格式
第一行两个整数 。第二行一个整数 。接下来 行,每行一个整数 。
输出格式
输出 行,第 行为对应询问的答案。
数据范围
,,,。
样例 1
输入
4 0
3
1
2
3
输出
0
2
2
样例 2
输入
2 100
1
1
输出
1
样例 3
输入
314159 26535
5
271
828
1828
45904
52353
输出
765557189
351184939
258247317
305813889
68486796