题目分析

我们有一个 $n$ 个点的有向图，满足：

• 每个点最多一条出边（即出度 ≤ 1）
• 每个点的入度必须在集合 $S$ 中
• 边有 $k$ 种颜色

由于是 DAG 且每个点出度 ≤ 1，整个图由若干条链和若干孤立点组成。

---

关键观察

1. 图的结构：每个连通分量是一条链（可能长度为 1，即孤立点）
2. 入度约束：每个点的入度 ∈ $S$
3. 出度约束：每个点出度 ≤ 1

这意味着：

• 链的起点：入度 ∈ $S$，出度 = 1
• 链的中间点：入度 = 1 ∈ $S$，出度 = 1
• 链的终点：入度 = 1 ∈ $S$，出度 = 0
• 孤立点：入度 = 0 ∈ $S$，出度 = 0

---

组合计数

设 $S$ 中元素为 $d_1, d_2, \dots, d_m$。

1. 链的计数

考虑一条长度为 $L$ 的链：

• 需要 $L$ 个不同的点
• 有 $L-1$ 条边，每条边有 $k$ 种颜色选择 ⇒ $k^{L-1}$ 种染色方式
• 点的排列：从 $n$ 个点中选 $L$ 个并按链顺序排列 ⇒ $P(n, L) = \frac{n!}{(n-L)!}$

2. 入度约束检查

对于一条长度为 $L$ 的链：

• 起点：入度必须 ∈ $S$（但起点入度实际为 0，所以要求 $0 \in S$）
• 中间点：入度 = 1，所以要求 $1 \in S$
• 终点：入度 = 1，要求 $1 \in S$

重要：如果 $1 \notin S$，则不能有长度 ≥ 2 的链！

3. 图的分解

整个图是若干条链和孤立点的不相交并。

设 $f_i$ = 长度为 $i$ 的链的生成函数（带权计数），考虑指数生成函数：

对于长度 $L$ 的链：

• 如果 $L = 1$（孤立点）：要求 $0 \in S$，权重 = 1（无边）
• 如果 $L \geq 2$：要求 $0 \in S$ 且 $1 \in S$，权重 = $k^{L-1}$

但注意：链的起点入度 0 ∈ S，中间点和终点入度 1 ∈ S。

---

生成函数解法

设 $a_t$ = 长度为 $t$ 的链的个数（带排列和颜色权重）：

• $t=1$：$a_1 = n \cdot [0 \in S]$
• $t\geq 2$：$a_t = \frac{n!}{(n-t)!} \cdot k^{t-1} \cdot [0 \in S] \cdot [1 \in S]$

但这样直接计数会重复，因为链的顺序无关。

正确做法：设 $f_t$ = 由 $t$ 个点组成的图的方案数（EGF）。

实际上，这是一个有标号集合划分问题，每个块是一条链。

---

动态规划解法

设 $dp[i]$ = $i$ 个点的图的方案数。

转移：考虑最后一个点所在的链长度 $j$：

• $j=1$（孤立点）：需 $0 \in S$，方案数 = $dp[i-1]$
• $j\geq 2$：需 $0 \in S$ 且 $1 \in S$，从 $i$ 个点中选 $j$ 个构成链，方案数 = $\binom{i-1}{j-1} \cdot (j-1)! \cdot k^{j-1} \cdot dp[i-j]$

但 $\binom{i-1}{j-1} \cdot (j-1)! = \frac{(i-1)!}{(i-j)!}$

所以：

$$dp[i] = [0 \in S] \cdot dp[i-1] + [0 \in S] \cdot [1 \in S] \cdot \sum_{j=2}^i \frac{(i-1)!}{(i-j)!} \cdot k^{j-1} \cdot dp[i-j] $$

这可以得到 $O(n^2)$ 做法，但 $n$ 太大需要优化。

---

高效做法

注意到 $S \subseteq \{0,1,2,3\}$，情况有限，可以分类讨论。

情况 1：$S = \{0\}$

只能有孤立点，答案 = $1$。

情况 2：$S = \{1\}$

只能形成若干个二元环（但题目要求是 DAG，所以不能有环！）⇒ 无解，答案 = $0$？
等等，DAG 且每个点入度 = 1，出度 ≤ 1 ⇒ 只能是链，但链的起点入度 = 0 ∉ S，矛盾 ⇒ 答案 = $0$。

情况 3：$S = \{0,1\}$（重要）

这是最复杂的情况，图是若干链，链长任意，但要求链的起点入度 0 ∈ S，中间点和终点入度 1 ∈ S。

设 $F(n)$ = $n$ 个点的答案。

• 要么第一个点是孤立点：$F(n-1)$
• 要么第一个点在长度为 $j$ 的链中：选 $j-1$ 个后续点，排列成链（$(j-1)!$ 种），边有 $k^{j-1}$ 种颜色，剩余 $n-j$ 个点任意：$\binom{n-1}{j-1} \cdot (j-1)! \cdot k^{j-1} \cdot F(n-j)$

所以：

$$F(n) = F(n-1) + \sum_{j=2}^n \frac{(n-1)!}{(n-j)!} \cdot k^{j-1} \cdot F(n-j) $$

设 $G(n) = \frac{F(n)}{(n-1)!}$（$n\geq 1$），可以化成卷积形式，用生成函数求解。

---

矩阵快速幂优化

对于 $S = \{0,1\}$，递推式：

$$F(n) = F(n-1) + \sum_{j=2}^n \frac{(n-1)!}{(n-j)!} k^{j-1} F(n-j) $$

可以写成：

$$\frac{F(n)}{(n-1)!} = \frac{F(n-1)}{(n-1)!} + \sum_{j=2}^n \frac{k^{j-1}}{(j-1)!} \cdot \frac{F(n-j)}{(n-j)!} $$

令 $f(n) = \frac{F(n)}{n!}$，则：

$$n f(n) = f(n-1) + \sum_{j=2}^n \frac{k^{j-1}}{(j-1)!} \cdot (n-1) f(n-j) $$

这仍然复杂。实际上，对于 $S=\{0,1\}$，已知公式：

$$F(n) = \sum_{i=0}^n \frac{n!}{(n-i)!} \cdot (k+1)^{\binom{i}{2}} \cdot ??? $$

（此处需要更精细推导）

---

最终公式（经过推导）

对于一般 $S$，记：

• $c_0 = [0 \in S]$
• $c_1 = [1 \in S]$

则答案的 EGF 是：

$$F(x) = \exp\left( c_0 x + c_1 \frac{k x^2}{2} \right) $$

解释：

• $c_0 x$：孤立点（长度 1 的链）
• $c_1 \frac{k x^2}{2}$：长度为 2 的链（一条边，k 种颜色）

但这是错的，因为链长 > 2 的情况没考虑。实际上，长度为 $L$ 的链的 EGF 是：

$$\frac{k^{L-1}}{L} x^L \cdot [0 \in S] \cdot [1 \in S]^{L-1} $$

所以：

$$F(x) = \exp\left( [0 \in S] x + [1 \in S] \sum_{L\geq 2} \frac{k^{L-1}}{L} x^L \right) $$

求和：

$$\sum_{L\geq 2} \frac{k^{L-1}}{L} x^L = \frac{1}{k} \sum_{L\geq 2} \frac{(kx)^L}{L} = \frac{1}{k} \left( -\ln(1-kx) - kx \right) $$

所以：

$$F(x) = \exp\left( [0 \in S] x - [1 \in S] x + \frac{[1 \in S]}{k} (-\ln(1-kx)) \right) $$

即：

$$F(x) = (1-kx)^{-[1 \in S]/k} \cdot e^{([0 \in S] - [1 \in S]) x} $$

那么答案就是 $n! \cdot [x^n] F(x)$。

---

最终算法

1. 读入 $n, k, S$
2. 计算 $c_0 = [0 \in S]$, $c_1 = [1 \in S]$
3. 如果 $c_0 == 0$ 且 $c_1 == 0$，答案 = 0
4. 如果 $c_1 == 0$，答案 = $c_0^n \cdot n!$（实际上只有孤立点，答案 = $[n==0]$？不对，n 个点每个点都可以是孤立点 ⇒ $1$ 种方案？其实是 1，因为只有一种方式：所有点孤立）
   • 仔细想：n 个标号点，每个点孤立，只有 1 种图（无边），所以答案 = 1。
5. 如果 $c_0 == 0$ 且 $c_1 == 1$，这是入度全为 1，出度 ≤ 1，只能是 n 个点成环（但 DAG 不能有环）⇒ 答案 = 0
6. 一般情况（$c_0=1, c_1=1$）：
   根据公式：$$F(x) = (1-kx)^{-1/k} \cdot e^{0\cdot x} = (1-kx)^{-1/k} $$展开：$$[x^n] F(x) = \binom{-1/k}{n} (-k)^n = \frac{(1/k)(1/k+1)\cdots(1/k+n-1)}{n!} k^n $$所以：$$ans = n! \cdot [x^n] F(x) = \prod_{i=0}^{n-1} (1 + k i) $$注意这个乘积模 998244353，n 很大时不能直接算，但 $k$ 很小，可以分段打表或公式化简。

---

代码实现（框架）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    long long n, k;
    int m;
    cin >> n >> k >> m;
    
    set<int> S;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        S.insert(x);
    }
    
    bool c0 = S.count(0);
    bool c1 = S.count(1);
    
    if (!c0 && !c1) {
        cout << 0 << endl;
        return 0;
    }
    
    if (!c1) {
        // 只有孤立点
        cout << 1 << endl;
        return 0;
    }
    
    if (!c0) {
        // 只有入度1，DAG不可能
        cout << 0 << endl;
        return 0;
    }
    
    // c0=1, c1=1 的一般情况
    // ans = prod_{i=0}^{n-1} (1 + k*i) mod MOD
    long long ans = 1;
    for (long long i = 0; i < n; i++) {
        ans = (ans * (1 + k * i % MOD)) % MOD;
    }
    cout << ans << endl;
    
    return 0;
}

注意：直接乘 $n$ 次对于 $n=9\times 10^8$ 太大，需要更高效方法（利用多项式或分块打表）。

---

总结

本题的关键在于理解图是链的集合，然后根据 $S$ 的内容分类讨论，最后利用生成函数得到闭形式，再针对大数据范围进行优化。