分数: 900 点
问题陈述
对于非负整数 x 和 k, k- 第一个最低数字 x 是余数 \bigl\lfloor \frac{x}{10^k}\bigr\rfloor 除以 10。例如, 0-th, 1-st, 2-nd,和 3-rd 的最低数字 123 是 3, 2, 1,和 0。
给你正整数 N, M, K,以及非负整数序列 A = (A_1, \ldots, A_N) 和 B = (B_1, \ldots, B_N).
考虑重新安排 A 通过以下过程。
- 执行以下操作 M 次。
- 选择一个整数 k 这样 0\leq k \leq K - 1.
- 然后,对 A by k- 第最低数字。也就是说,让 A^{(d)} 是以下序列 A 由以下所有元素组成 A 谁 k- 第最低数字是 d,并替换 A 串联 A^{(0)}, A^{(1)}, \ldots, A^{(9)} 按此顺序。
有 K^M 执行此过程的方法。他们中有多少人最终成为了 A 等于 B?求这个计数的模数 998244353.
约束
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 10^9
- 1\leq K\leq 18
- 0\leq A_i < 10^K
- 0\leq B_i < 10^K
- A 和 B 作为多重集是相等的。也就是说,每个整数 x 出现相同次数 A 和 B.
输入
输入由标准输入按以下格式给出:
N M K A_1 \ldots A_N B_1 \ldots B_N
输出
打印数字,模数 998244353,执行最终流程的方法 A 等于 B.
示例输入 1
3 2 3 74 42 54 42 54 74
示例输出 1
5
让 k_1 和 k_2 是 分别在第一次和第二次迭代中选择 k 。例如,如果 k_1 = 0 和 k_2 = 1,那么 A 更改如下。
- 稳定的排序方式 k_1-th (0-th) 最低数字使 A = (42,74,54).
- 稳定的排序方式 k_2-th (1-st) 最低数字使 A = (42,54,74).
以下是执行该过程的所有方法以及结果 A.
- (k_1, k_2) = (0,0): A = (42,74,54).
- (k_1, k_2) = (0,1): A = (42,54,74).
- (k_1, k_2) = (0,2): A = (42,74,54).
- (k_1, k_2) = (1,0): A = (42,54,74).
- (k_1, k_2) = (1,1): A = (42,54,74).
- (k_1, k_2) = (1,2): A = (42,54,74).
- (k_1, k_2) = (2,0): A = (42,74,54).
- (k_1, k_2) = (2,1): A = (42,54,74).
- (k_1, k_2) = (2,2): A = (74,42,54).
示例输入 2
2 1 1 2 3 3 2
示例输出 2
0
无法满足条件。
示例输入 3
5 100 4 0 12 34 56 78 0 12 34 56 78
示例输出 3
982924732
全部 4^{100} 方式满足条件。