1574F - Occurrences 详细题解

题意简述

给定 $n$ 个模式串 $A_1,A_2,\dots,A_n$，以及整数 $k,m$。 我们要构造一个长度恰好为 $m$ 的数组 $a$，元素取自 $[1,k]$，满足： 对每一个模式串 $A_i$，$A_i$ 在 $a$ 中的出现次数，不小于 $A_i$ 的任意一个非空子串在 $a$ 中的出现次数。

求合法数组 $a$ 的数量，答案对 $998244353$ 取模。

---

一、条件翻译与简化

核心约束：

$$\operatorname{cnt}(A_i) \ge \operatorname{cnt}(t) \quad \forall \text{非空子串 } t \text{ 属于 } A_i $$

1. 模式串内部有重复元素的情况

若 $A_i$ 中有重复元素（例如 $A_i=[1,2,1]$）：

• 单个元素 $1$ 是 $A_i$ 的子串；
• 每出现一次 $A_i$，至少会出现两次 $1$；
• 因此必然有 $\operatorname{cnt}(1) > \operatorname{cnt}(A_i)$，违反条件。

结论： 所有出现在含重复元素的模式串中的数字，都不能出现在最终数组 $a$ 中，这些数字称为禁用数字。

2. 模式串内部无重复元素的情况

对元素互不相同的 $A_i=[x_1,x_2,\dots,x_t]$，约束会强制：

• 数组 $a$ 中，只要出现 $x_j$，下一个元素一定是 $x_{j+1}$；
• 只要出现 $x_{j+1}$，前一个元素一定是 $x_j$。

也就是说： 这些数字的前后相邻关系被唯一固定，不能随意排列。

---

二、建图：相邻关系建模

把 $1\sim k$ 每个数字看作有向图顶点：

• 对每个合法 $A_i$，对相邻元素连边：$x_j \rightarrow x_{j+1}$；
• 每个点的入边、出边都最多保留一条（关系唯一）。

该图结构只会由若干链和环组成，因为每个点入度、出度均不超过 $1$。

---

三、筛选合法连通块

我们对图求弱连通分量（不看方向连通），并判断是否可用：

一个分量是合法（好）分量，当且仅当同时满足：

1. 分量内无禁用数字；
2. 每个点入度 $\le 1$、出度 $\le 1$；
3. 分量是链，不是环：
   • 链：恰好一个入度为 $0$ 的起点，一个出度为 $0$ 的终点；
   • 环：没有起点终点，会无限循环，与有限长数组矛盾，直接禁用。

最终结论： 合法数组 $a$ 只能由若干完整的好链拼接而成，链不能拆分、不能打乱顺序，链可以重复使用。

---

四、动态规划计数

设：

• $cnt[l]$：长度为 $l$ 的好链的条数；
• $dp[i]$：构造长度为 $i$ 的合法数组的方案数。

初始状态

$$dp[0] = 1$$

空数组有且仅有一种方案。

转移方程

$$dp[i] = \sum_{\substack{l=1 \\ cnt[l]>0}}^k dp[i-l] \times cnt[l] \quad (i \ge l) $$

含义：在长度为 $i-l$ 的合法数组后，拼接一条长度为 $l$ 的好链。

答案

$$dp[m]$$

---

五、复杂度说明

• 直接 DP 复杂度为 $O(mk)$，会超时；
• 好链的长度种类只有 $O(\sqrt k)$ 种，只遍历有效长度即可优化到 $O(m\sqrt k)$，可以通过本题。