3823. 字符串计数

【题目描述】

字符集大小为 $m$。给定一个长为 $k$ 的字符串 $s$，求出所有长为 $n$ 的串中，不包含子串 $s$ 的共有几个。

【输入格式】

第一行三个整数 $n,m,k$。

第二行 $k$ 个整数，第 $i$ 个表示 $s_i$ 在字符集中的编号。

【输出格式】

一个整数表示答案。答案对 $998244353$ 取模。

【样例输入】

3 2 2
1 2

【样例输出】

4

【样例说明】

$4$ 种方案分别是： $111,211,221,222$。

【数据规模与约定】

对于$50\%$数据，$1 \leq n \leq 10^3$。

对于$100\%$数据，$1 \leq n,m,k \leq 10^5$。

$1 \leq s_i \leq m$。

【来源】

生成函数的运算与组合计数问题——杭州学军中学——金策——2015CTS论文相关