Long Sequence Inversion 2

AtCoder

IDttpc2024_1_l

Time2000ms

Memory256MB

Difficulty—

In this problem, when we refer to a "permutation of length $K$", we mean a permutation of $(0, 1, \dots, K - 1)$. Also, we denote the $k$\-th element ($0$\-based) of a sequence $X$ as $X[k]$. You are given a permutation $P$ of length $L$, and $L$ permutations of length $B$, denoted as $V_{0}, V_{1}, \dots, V_{L - 1}$. We define a sequence $A$ of length $B^L$ as follows: > For each $0 ≤ n < B^L$, when $n$ is represented as an $L$\-digit number in base $B$, let $N[i]$ be the value at the $B^i$ place ($0 ≤ i < L$). Then, > > $\displaystyle A[n] = \sum_{i=0}^{L-1} V_i[N[i]] \cdot B^{P[i]}$ Find the inversion number of the sequence $A$ modulo $998244353$. ## Constraints * All input values are integers * $1 \leq L$ * $2 \leq B$ * $L \times (B + 1) \leq 5 \times 10^{5}$ * $P$ is a permutation of length $L$ * For each $0 \leq i < L$, $V_{i}$ is a permutation of length $B$ ## Input Input is given from standard input in the following format: $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]$ [samples]

Samples

Input #1

Output #1

14

For example, when $n = 5$, since $N = (1, 0, 1)$, we have $A[5] = V_{0}[1] \cdot 2^{P[0]} + V_{1}[0] \cdot 2^{P[1]} + V_{2}[1] \cdot 2^{P[2]}=3$.  
By calculating similarly, we get $A = (5, 1, 4, 0, 7, 3, 6, 2)$. The inversion count of $A$ is $14$, so output $14$.

Input #2

Output #2

60

$A = (9, 1, 13, 5, 10, 2, 14, 6, 11, 3, 15, 7, 8, 0, 12, 4)$. The inversion count of $A$ is $60$, so output $60$.

Input #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

Output #3

138876070

Output the answer modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Long Sequence Inversion 2",
    "description": {
      "content": "In this problem, when we refer to a \"permutation of length $K$\", we mean a permutation of $(0, 1, \\dots, K - 1)$. Also, we denote the $k$\\-th element ($0$\\-based) of a sequence $X$ as $X[k]$. You are ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "ttpc2024_1_l"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In this problem, when we refer to a \"permutation of length $K$\", we mean a permutation of $(0, 1, \\dots, K - 1)$. Also, we denote the $k$\\-th element ($0$\\-based) of a sequence $X$ as $X[k]$.\nYou are ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments