AT_arc149_e.[ARC149E] Sliding Window Sort

给定正整数 $N$、$M$、$K$。考虑对正整数序列 $A = (A_0, \ldots, A_{N-1})$ 进行如下操作：

• 按照 $k = 0, 1, \ldots, K-1$ 的顺序，依次进行以下操作：
  • 将 $A_{k\bmod N},\ A_{(k+1)\bmod N},\ \ldots,\ A_{(k+M-1)\bmod N}$ 升序排序。也就是说，将 $A_{k\bmod N},\ A_{(k+1)\bmod N},\ \ldots,\ A_{(k+M-1)\bmod N}$ 按从小到大排列为 $(x_0, \ldots, x_{M-1})$ 时，对于每个 $0 \leq j < M$，用 $x_j$ 替换 $A_{(k+j)\bmod N}$。

给定一个由 $1$ 到 $N$ 之间的整数构成的排列 $B = (B_0, \ldots, B_{N-1})$。请你计算有多少个正整数序列 $A$，使得经过上述操作后，$A$ 恰好变为 $B$。请将答案对 $998244353$ 取模后输出。

输入以如下格式从标准输入读入：

$N$ $M$ $K$ $B_0$ $B_1$ $\ldots$ $B_{N-1}$

输出满足条件的正整数序列 $A$ 的个数，对 $998244353$ 取模后的结果。

限制条件

• $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$
• 如果 $i \neq j$，则 $B_i \neq B_j$

样例解释 1

例如 $A = (4,1,5,6,2,3)$ 满足条件。对于该 $A$，操作过程如下：

• $k=0$ 时，$A$ 变为 $(1,4,5,6,2,3)$。
• $k=1$ 时，$A$ 变为 $(1,4,5,6,2,3)$。
• $k=2$ 时，$A$ 变为 $(1,4,2,5,6,3)$。
• $k=3$ 时，$A$ 变为 $(1,4,2,3,5,6)$。
• $k=4$ 时，$A$ 变为 $(6,4,2,3,1,5)$，与 $B$ 一致。

样例解释 2

不存在满足条件的 $A$。

样例解释 3

所有由 $1$ 到 $20$ 组成的排列都满足条件。

由 ChatGPT 4.1 翻译