Random Radix Sort

AtCoder

IDarc158_f

Time4000ms

Memory256MB

Difficulty—

For non-negative integers $x$ and $k$, the $k$\-th lowest digit of $x$ is the remainder when $\bigl\lfloor \frac{x}{10^k}\bigr\rfloor$ is divided by $10$. For instance, the $0$\-th, $1$\-st, $2$\-nd, and $3$\-rd lowest digits of $123$ are $3$, $2$, $1$, and $0$, respectively. You are given positive integers $N$, $M$, $K$, and sequences of non-negative integers $A = (A_1, \ldots, A_N)$ and $B = (B_1, \ldots, B_N)$. Consider rearranging $A$ by the following process. * Do the following $M$ times. * Choose an integer $k$ such that $0\leq k \leq K - 1$. * Then, perform a stable sort on $A$ by $k$\-th lowest digit. That is, let $A^{(d)}$ be the subsequence of $A$ composed of all elements of $A$ whose $k$\-th lowest digits are $d$, and replace $A$ with the concatenation of $A^{(0)}, A^{(1)}, \ldots, A^{(9)}$ in this order. There are $K^M$ ways to execute this process. How many of them end up making $A$ equal $B$? Find this count modulo $998244353$. ## Constraints * $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$ and $B$ are equal as multisets. That is, every integer $x$ occurs the same number of times in $A$ and $B$. ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ $A_1$ $\ldots$ $A_N$ $B_1$ $\ldots$ $B_N$ [samples]

Samples

Input #1

3 2 3
74 42 54
42 54 74

Output #1

5

Let $k_1$ and $k_2$ be the $k$ chosen in the first and second iterations, respectively. For instance, if $k_1 = 0$ and $k_2 = 1$, then $A$ changes as follows.

*   A stable sort by $k_1$\-th ($0$\-th) lowest digit makes $A = (42,74,54)$.
*   A stable sort by $k_2$\-th ($1$\-st) lowest digit makes $A = (42,54,74)$.

Here are all the ways to execute the process and the resulting $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)$.

Input #2

2 1 1
2 3
3 2

Output #2

0

There is no way to satisfy the condition.

Input #3

5 100 4
0 12 34 56 78
0 12 34 56 78

Output #3

982924732

All $4^{100}$ ways satisfy the condition.

API Response (JSON)

{
  "problem": {
    "name": "Random Radix Sort",
    "description": {
      "content": "For non-negative integers $x$ and $k$, the $k$\\-th lowest digit of $x$ is the remainder when $\\bigl\\lfloor \\frac{x}{10^k}\\bigr\\rfloor$ is divided by $10$. For instance, the $0$\\-th, $1$\\-st, $2$\\-nd, ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc158_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For non-negative integers $x$ and $k$, the $k$\\-th lowest digit of $x$ is the remainder when $\\bigl\\lfloor \\frac{x}{10^k}\\bigr\\rfloor$ is divided by $10$. For instance, the $0$\\-th, $1$\\-st, $2$\\-nd, ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments