CF1654H Three Minimums

给定一个互不相同的数值序列，我们将最小值、次小值和第三小值分别称为“第一最小值”、“第二最小值”和“第三最小值”（按递增顺序排列）。 如果一个排列 $p_1, p_2, \dots, p_n$ 满足如下条件，则称其为“好排列”：对于所有满足 $1 \le l < l+2 \le r \le n$ 的区间 $(l, r)$，都有： - 如果 $\{p_l, p_r\}$（顺序不限）是区间 $p_l, p_{l+1}, \dots, p_r$ 的第一最小值和第二最小值，则该区间的第三最小值必须是 $p_{l+1}$ 或 $p_{r-1}$。 现在给定一个整数 $n$ 和一个长度为 $m$ 的字符串 $s$，$s$ 仅包含字符“”。 请统计满足以下条件的“好排列” $p_1, p_2, \dots, p_n$ 的个数，并对 $998\,244\,353$ 取模： - 对于所有 $1 \le i \le m$， - 若 $s_i$ 为“”，则 $p_i > p_{i+1}$。 由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \leq m \leq \min(100, n-1)$）。 第二行包含一个长度为 $m$ 的字符串 $s$，仅由字符“”组成。

输出一个整数，表示满足题意的“好排列”个数，对 $998\,244\,353$ 取模。

在第一个样例中，有 $5$ 个满足字符串 $s$ 所给限制的“好排列”： $[4, 3, 2, 1, 5]$，$[5, 3, 2, 1, 4]$，$[5, 4, 2, 1, 3]$，$[5, 4, 3, 1, 2]$，$[5, 4, 3, 2, 1]$。 它们都： - 是“好排列”； - 满足 $p_1 > p_2$； - 满足 $p_2 > p_3$； - 满足 $p_3 > p_4$。 在第二个样例中，有 $60$ 个排列满足 $p_1 < p_2$，其中只有 $56$ 个是“好排列”：排列 $[1, 4, 3, 5, 2]$，$[1, 5, 3, 4, 2]$，$[2, 4, 3, 5, 1]$，$[2, 5, 3, 4, 1]$ 不是“好排列”，因为对于区间 $(l, r) = (1, 5)$，不满足要求。例如排列 $[2, 4, 3, 5, 1]$： - 第一最小值和第二最小值分别为 $p_5$ 和 $p_1$（即 $\{p_l, p_r\}$，顺序不限）； - 第三最小值为 $p_3$（既不是 $p_{l+1}$ 也不是 $p_{r-1}$）。 在第三个样例中，有 $23$ 个满足字符串 $s$ 所给限制的“好排列”： $[1, 2, 4, 3, 6, 5]$，$[1, 2, 5, 3, 6, 4]$，$[1, 2, 6, 3, 5, 4]$，$[1, 3, 4, 2, 6, 5]$，$[1, 3, 5, 2, 6, 4]$，$[1, 3, 6, 2, 5, 4]$，$[1, 4, 5, 2, 6, 3]$，$[1, 4, 6, 2, 5, 3]$，$[1, 5, 6, 2, 4, 3]$，$[2, 3, 4, 1, 6, 5]$，$[2, 3, 5, 1, 6, 4]$，$[2, 3, 6, 1, 5, 4]$，$[2, 4, 5, 1, 6, 3]$，$[2, 4, 6, 1, 5, 3]$，$[2, 5, 6, 1, 4, 3]$，$[3, 4, 5, 1, 6, 2]$，$[3, 4, 5, 2, 6, 1]$，$[3, 4, 6, 1, 5, 2]$，$[3, 4, 6, 2, 5, 1]$，$[3, 5, 6, 1, 4, 2]$，$[3, 5, 6, 2, 4, 1]$，$[4, 5, 6, 1, 3, 2]$，$[4, 5, 6, 2, 3, 1]$。 由 ChatGPT 4.1 翻译