← 返回题目列表

AtCoder · arc158_f

F. 随机基数排序

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

分数: 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} 方式满足条件。