Sliding Window Sort

AtCoder

IDarc149_e

Time2000ms

Memory256MB

Difficulty—

You are given positive integers $N$, $M$, and $K$. Consider the following operation on a sequence of positive integers $A = (A_0, \ldots, A_{N-1})$. * Do the following for $k=0, 1, \ldots, K-1$ in this order. * Sort $A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N}$ in ascending order. That is, replace $A_{(k+j)\bmod N}$ with $x_j$ for each $0\leq j < M$, where $(x_0, \ldots, x_{M-1})$ is the result of sorting $A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N}$ in ascending order. You are given a permutation $B = (B_0, \ldots, B_{N-1})$ of the integers from $1$ through $N$. Find the number of sequences $A$ of positive integers that will equal $B$ after performing the operation above, modulo $998244353$. ## Constraints * $2\leq N\leq 3\times 10^5$ * $2\leq M\leq N$ * $1\leq K\leq 10^9$ * $1\leq B_i\leq N$ * $B_i\neq B_j$ if $i\neq j$. ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ $B_0$ $\ldots$ $B_{N-1}$ [samples]

Samples

Input #1

6 3 5
6 4 2 3 1 5

Output #1

18

For instance, $A = (4,1,5,6,2,3)$ satisfies the condition. On this $A$, the operation will proceed as follows.

*   The action for $k=0$ changes $A$ to $(1,4,5,6,2,3)$.
*   The action for $k=1$ changes $A$ to $(1,4,5,6,2,3)$.
*   The action for $k=2$ changes $A$ to $(1,4,2,5,6,3)$.
*   The action for $k=3$ changes $A$ to $(1,4,2,3,5,6)$.
*   The action for $k=4$ changes $A$ to $(6,4,2,3,1,5)$, which equals $B$.

Input #2

6 3 5
6 5 4 3 2 1

Output #2

0

No sequence $A$ satisfies the condition.

Input #3

20 20 149
13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12

Output #3

401576539

All permutations of the integers from $1$ through $20$ satisfy the condition.

API Response (JSON)

{
  "problem": {
    "name": "Sliding Window Sort",
    "description": {
      "content": "You are given positive integers $N$, $M$, and $K$. Consider the following operation on a sequence of positive integers $A = (A_0, \\ldots, A_{N-1})$. *   Do the following for $k=0, 1, \\ldots, K-1$ in ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc149_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given positive integers $N$, $M$, and $K$. Consider the following operation on a sequence of positive integers $A = (A_0, \\ldots, A_{N-1})$.\n\n*   Do the following for $k=0, 1, \\ldots, K-1$ in ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments