分数: 100 点
问题陈述
在这个问题中,当我们提到“长度的排列 K“,我们的意思是排列 (0, 1, \dots, K - 1)。另外,我们表示 序列的 k- 第一个元素 (0-基于) X as X[k].
给你一个排列 P 长度 L,和 L 长度排列 B,表示为 V_{0}, V_{1}, \dots, V_{L - 1}.
我们定义一个序列 A 长度 B^L 如下:
对于每个 0 ≤ n < B^L,当 n 表示为 L- 基数中的数字 B,让 N[i] 是处的值 B^i 地点(0 ≤ i < L)。然后,\displaystyle A[n] = \sum_{i=0}^{L-1} V_i[N[i]] \cdot B^{P[i]}
求序列的倒数 A 模数 998244353.
约束
- 所有输入值均为整数
- 1 \leq L
- 2 \leq B
- L \times (B + 1) \leq 5 \times 10^{5}
- P 是长度的排列 L
- 对于每个 0 \leq i < L, V_{i} 是长度的排列 B
输入
输入是从标准输入按以下格式给出的:
L B
P[0] P[1] \cdots P[L - 1]
V_{0}[0] V_{0}[1] \cdots V_{0}[B - 1]
\vdots
V_{L - 1}[0] V_{L - 1}[1] \cdots V_{L - 1}[B - 1]
输出
打印答案。
示例输入 1
3 2 2 0 1 1 0 1 0 0 1
示例输出 1
14
例如,当 n = 5,因为 N = (1, 0, 1),我们有 A[5] = V_{0}[1] \cdot 2^{P[0]} + V_{1}[0] \cdot 2^{P[1]} + V_{2}[1] \cdot 2^{P[2]}=3.
通过类似的计算,我们得到 A = (5, 1, 4, 0, 7, 3, 6, 2)。的反转计数为 A is 14,所以输出 14.
示例输入 2
2 4 1 0 2 0 3 1 1 2 3 0
示例输出 2
60
A = (9, 1, 13, 5, 10, 2, 14, 6, 11, 3, 15, 7, 8, 0, 12, 4)。的反转计数为 A is 60,所以输出 60.
示例输入 3
9 10 2 5 7 3 8 1 4 6 0 9 2 4 0 1 6 7 3 5 8 4 1 6 7 8 0 5 9 2 3 1 9 2 4 6 8 5 7 0 3 9 0 8 2 5 1 6 7 3 4 1 6 0 7 3 9 2 4 5 8 4 5 2 9 1 6 7 3 0 8 7 0 5 6 1 9 2 4 3 8 3 2 1 6 7 0 8 9 4 5 9 2 4 3 5 8 0 6 7 1
示例输出 3
138876070
输出答案模数 998244353.