← 返回题目列表

AtCoder · ttpc2024_1_l

L. 长序列反转 2

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

分数: 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.