P11959 「ZHQOI R1」诗歌

 淡く煌(きらめ)く傷口が 瞬間 世界を止めて ------------ 长夜伴浪破晓梦，梦晓破浪伴夜长。

给定正整数 $k$，本题的字符集大小为 $k$，我们用正整数 $i$ 来表示字符集中的第 $i$ 个字符。 给定正整数 $m$，定义一个字符串 $\mathcal{S}$ 为「动听」的，当且仅当 $\mathcal{S}$ 的长度小于 $m+2$，或在 $\mathcal{S}$ 中**任意**删除恰好 $m$ 个字符后都不存在一个长度大于 $1$ 的回文连续子串。 你需要处理 $q$ 次询问，每次给定一个长度为 $m+2$ 且「动听」的字符串 $T$，和一个不可重字符集合 $U$，试求出有几个长度为 $n$ 的字符串，满足以下条件： - $T$ 为该字符串的一段前缀 - 该字符串是「动听」的 - 字符串最后一位属于 $U$ 答案对 $998244353$ 取模。对于每组询问，$k$ 和 $m$ 是相同的。 **注意：本题数据保证 $k-m\ge3$。**

第一行包含一个整数 $c$ 表示测试点编号。样例满足 $c = 0$。 第二行包含四个整数 $q,k,m$。分别表示询问次数、字符集大小和判定字符串为「动听」时所用到的常数。 接下来 $q$ 行，每行包含一个询问。依次输入一个正整数 $n$，一个长度为 $m+2$ 的正整数序列 $T$，一个正整数 $|U|$ 表示集合 $U$ 的大小，和 $|U|$ 个正整数表示 $U$ 中的元素。其定义见题目描述。

对于每次询问，输出一行一个整数表示所求的答案。

**【样例 1 解释】** 相当于给定一个串 `abc`，$U = \{a\}$，字符集合为 $\{a,b,c,d,e\}$，询问有多少长度为 $5$ 的串满足题意，容易发现有且仅有以下 $2$ 个： ```plain abcda abcea ``` 故答案为 $2$。 **【样例 2 解释】** 相当于给定一个串 `abc`，$U = \{a,b\}$，字符集合为 $\{a,b,c,d,e\}$，询问有多少长度为 $7$ 的串满足题意，容易发现有且仅有以下 $6$ 个： ```plain abceadb abcdeab abcedba abcdeba abcedab abcdaeb ``` 故答案为 $6$。 **【数据范围】** 对于所有测试点保证：$1 \leq n \leq 10^7$，$1 \leq q,m \leq 2 \times 10^3$，$m + 3 \leq k\le 10^9$，$U \subseteq [1,k]$，$T_i \in [1,k]$。 |测试点编号|$q=$|$n\le$|$m=$|$\sum\vert U\vert=$|特殊性质| |:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$700$|$700$|$100$|$700$|$k-m=3$| |$2$|$700$|$700$|$100$|$700$|无| |$3$|$10^3$|$5\times 10^5$|$20$|$4\times 10^3$|无| |$4$|$2\times 10^3$|$5\times 10^5$|$100$|$4\times10^3$|无| |$5$|$2\times 10^3$|$5\times 10^5$|$100$|$10^6$|无| |$6$|$2\times 10^3$|$2.5\times 10^5$|$10^3$|$4\times 10^3$|无| |$7$|$2\times 10^3$|$5\times 10^5$|$2\times 10^3$|$4\times 10^3$|无| |$8$|$2\times 10^3$|$2.5\times 10^5$|$10^3$|$10^6$|无| |$9$|$2\times 10^3$|$5\times 10^5$|$2\times 10^3$|$10^6$|无| |$10$|$2\times 10^3$|$10^7$|$2\times 10^3$|$2\times 10^6$|无|