#P13658. [ARC149E] Sliding Window Sort

    ID: 12860 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-离散化不变量分析逆向还原操作前后缀最值乘法原理排列数计算

[ARC149E] Sliding Window Sort

题目描述

给定正整数 NN、MM、KK。考虑对正整数序列 A=(A0,…,AN−1)A = (A_0, \ldots, A_{N-1}) 进行如下操作:

  • 按照 k=0,1,…,K−1k = 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}$ 按从小到大排列为 (x0,…,xM−1)(x_0, \ldots, x_{M-1}) 时,对于每个 0≤j<M0 \leq j < M,用 xjx_j 替换 A(k+j) mod NA_{(k+j)\bmod N}。

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

输入格式

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

NN MM KK B0B_0 B1B_1 …\ldots BN−1B_{N-1}

输出格式

输出满足条件的正整数序列 AA 的个数,对 998244353998244353 取模后的结果。

输入输出样例 #1

输入 #1

6 3 5
6 4 2 3 1 5

输出 #1

18

输入输出样例 #2

输入 #2

6 3 5
6 5 4 3 2 1

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

401576539

说明/提示

限制条件

  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • 2≤M≤N2 \leq M \leq N
  • 1≤K≤1091 \leq K \leq 10^9
  • 1≤Bi≤N1 \leq B_i \leq N
  • 如果 i≠ji \neq j,则 Bi≠BjB_i \neq B_j

样例解释 1

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

  • k=0k=0 时,AA 变为 (1,4,5,6,2,3)(1,4,5,6,2,3)。
  • k=1k=1 时,AA 变为 (1,4,5,6,2,3)(1,4,5,6,2,3)。
  • k=2k=2 时,AA 变为 (1,4,2,5,6,3)(1,4,2,5,6,3)。
  • k=3k=3 时,AA 变为 (1,4,2,3,5,6)(1,4,2,3,5,6)。
  • k=4k=4 时,AA 变为 (6,4,2,3,1,5)(6,4,2,3,1,5),与 BB 一致。

样例解释 2

不存在满足条件的 AA。

样例解释 3

所有由 11 到 2020 组成的排列都满足条件。