#P9072. [CTS2023] 另一个欧拉数问题

[CTS2023] 另一个欧拉数问题

题目背景

你继续向前走,遇到了一个身着黑袍的老人,那边的门前放着一个巨大的沙盘,老人用手中的树枝在沙盘前画着奇怪的符号。

老人告诉你,他从年轻开始便梦想一个问题,直到他垂垂老矣,似乎也只揭露了答案的一角。

或许我该将它们交给你们了,老人说。

别太担心,我不想太为难你,至少我已经把必要的工具给你准备好了。

题目描述

对于正整数 α\alpha,考虑下述长为 αn\alpha n 的序列 aa

  • 对于每个 k=1,,nk=1,\dots, n,序列 aa 中出现了恰好 α\alphakk

  • 对于 i<ji < j 满足 ai=aja_i = a_j,那么对任意 i<k<ji < k < j,有 akaia_k \geq a_i

我们称满足上述要求的序列是一个 (n,α)(n,\alpha) 阶排列。

现在输入一个 (n0,α)(n_0,\alpha) 阶排列 PP。又给定 nnmm,请你计算有多少 (n,α)(n,\alpha) 阶排列包含子序列 PP,并且满足:

  • 总共有 mm 个下标 ii 满足 ai>ai+1a_i > a_{i+1}

你只需计算出这样的序列总数对 998244353998244353 取模的结果。

输入格式

第一行输入四个整数 α\alphannmmn0n_0

第二行输入 αn0\alpha n_0 个正整数,保证构成一个 (n0,α)(n_0,\alpha) 阶排列。

输出格式

输出一个整数,表示满足要求的序列的数量。

1 4 2 2
2 1
7
2 4 2 2
1 2 2 1
19

提示

【数据范围】

子任务 111010 分):保证 n2000n \leq 2000

子任务 221010 分):保证 α=1\alpha = 1n0=1n_0=1

子任务 333030 分):保证 α=1\alpha = 1

子任务 441515 分):保证 α=2\alpha = 2n0=1n_0=1

子任务 551515 分):保证 α=2\alpha = 2

子任务 662020 分):无特殊限制。

对于所有数据,保证 1n2×1051\leq n \leq 2\times 10^50m<n0\leq m < n1n0n1\leq n_0\leq n1αn02×1051\leq \alpha n_0 \leq 2\times 10^5

【提示】

为了方便选手处理形式幂级数的运算,我们提供了一个模板。选手可以根据自己的需要参考与使用该模板,也可以不使用该模板。