{"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 given a permutation $P$ of length $L$, and $L$ permutations of length $B$, denoted as $V_{0}, V_{1}, \\dots, V_{L - 1}$.  \nWe define a sequence $A$ of length $B^L$ as follows:\n\n> 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,\n> \n> $\\displaystyle A[n] = \\sum_{i=0}^{L-1} V_i[N[i]] \\cdot B^{P[i]}$\n\nFind the inversion number of the sequence $A$ modulo $998244353$.\n\n## Constraints\n\n*   All input values are integers\n*   $1 \\leq L$\n*   $2 \\leq B$\n*   $L \\times (B + 1) \\leq 5 \\times 10^{5}$\n*   $P$ is a permutation of length $L$\n*   For each $0 \\leq i < L$, $V_{i}$ is a permutation of length $B$\n\n## Input\n\nInput is given from standard input in the following format:\n\n$L$ $B$\n$P[0]$ $P[1]$ $\\cdots$ $P[L - 1]$\n$V_{0}[0]$ $V_{0}[1]$ $\\cdots$ $V_{0}[B - 1]$\n$\\vdots$\n$V_{L - 1}[0]$ $V_{L - 1}[1]$ $\\cdots$ $V_{L - 1}[B - 1]$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_l","tags":[],"sample_group":[["3 2\n2 0 1\n1 0\n1 0\n0 1","14\n\nFor 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$.  \nBy calculating similarly, we get $A = (5, 1, 4, 0, 7, 3, 6, 2)$. The inversion count of $A$ is $14$, so output $14$."],["2 4\n1 0\n2 0 3 1\n1 2 3 0","60\n\n$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$."],["9 10\n2 5 7 3 8 1 4 6 0\n9 2 4 0 1 6 7 3 5 8\n4 1 6 7 8 0 5 9 2 3\n1 9 2 4 6 8 5 7 0 3\n9 0 8 2 5 1 6 7 3 4\n1 6 0 7 3 9 2 4 5 8\n4 5 2 9 1 6 7 3 0 8\n7 0 5 6 1 9 2 4 3 8\n3 2 1 6 7 0 8 9 4 5\n9 2 4 3 5 8 0 6 7 1","138876070\n\nOutput the answer modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}