2026 CSP-S 模拟卷（一）T4 宴席安排

题目背景与题意

一场宴席要上 $n$ 道菜，每道菜只能从 $m$ 种原料中选一种作为主料。上菜是有顺序的，而某些相邻的主料搭配是不受欢迎的：题目给出 $k$ 对有序原料 $(x, y)$，表示紧挨着的两道菜中，前一道用原料 $x$ 而后一道用原料 $y$ 是不允许的。

请你统计：一共有多少种满足全部限制的完整上菜方案（即长度为 $n$ 的原料序列）？答案可能很大，请输出它对 $998244353$ 取模的结果。

注意 $k$ 对限制是有向的：$(1,2)$ 表示「1 后面不能紧接 2」，并不限制「2 后面紧接 1」。

输入格式

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

接下来 $k$ 行，每行两个整数 $x, y$，表示禁止「$x$ 后面紧接 $y$」。

输出格式

一行一个整数，表示方案数对 998244353 取模的结果。

样例输入

4 3 2
1 2
2 3

样例输出

37

样例解释

不允许的相邻搭配只有两种：1 2 与 2 3，其余相邻搭配都合法。长度为 4 的全部序列共 $3^4=81$ 个，其中满足限制的有 37 个。核对这个数最省事的办法是逐层数「以某种原料结尾的合法序列个数」：长度为 1 时三种原料各 1 个，得到向量 $(1,1,1)$；长度为 2 时，以原料 1 结尾的序列有 1 1、2 1、3 1 三个（禁止的是 1 2，不影响以 1 结尾）；以原料 2 结尾的有 2 2、3 2 两个（1 2 被禁止）；以原料 3 结尾的有 2 3 被禁止，只剩 1 3、3 3 两个。所以长度为 2 的向量是 $(3,2,2)$。按同样的规则逐层算：长度为 3 时是 $(7,4,5)$，长度为 4 时是 $(16,9,12)$，最后一次求和 $16+9+12=37$，与样例一致。

数据范围与子任务

对全部数据：$1 \le n \le 10^9$，$1 \le m \le 100$，$0 \le k \le m^2$，$1 \le x, y \le m$，$x \ne y$。保证给出的 $k$ 对限制互不相同。

子任务采用捆绑测试：子任务内部的测试点必须全部通过才能拿到该子任务的全部分值，否则该子任务得 0 分。

时间限制 2 秒，空间限制 512 MB。