菜王的 blog

题意简述

定义一个字符串 $a$ 中子序列 $b$ 的数量为满足 $\forall i, a_{p_i} = b_i$ 的长度为 $|b|$，值域为 $[1, |a|]$ 的严格单调递增正整数序列 $p$ 的个数。

定义一个只包含 L、I、F、E 四种字符的字符串是好的，当且仅当这个字符串中只存在恰好一个子序列 IF 与一个子序列 LIE。

请你求出 $A$ 个字符 L，$B$ 个字符 I，$C$ 个字符 F，$D$ 个字符 E 组成的共 $\frac{(A + B + C + D)!}{A!B!C!D!}$ 种不同的字符串中好的字符串的数量对 $10^9 + 7$ 取模的值。

此题多测，设 $T$ 为组数，对所有数据，满足 $1 \le T \le 2 \times 10^5$，$1 \le A, B, C, D \le 10^7$，$1 \le \sum B \le 2 \times 10^7$。

算法 1

我会爆搜！

时间复杂度：$\mathcal O(\frac{(A + B + C + D)!}{A!B!C!D!}poly(A + B + C + D))$。

期望得分：$10$。

算法 2

我会 DP！

考虑如何判断字符串 $a$ 中子序列 $b$ 是否出现了一次。我们可以这样做：

• 维护一个指针 $j$，初始 $j = 0$。
• 从 $1$ 到 $|a|$ 按顺序枚举 $i$：
  • 若 $j < |b|$ 且 $a_i = b_{j + 1}$，使 $j \gets j + 1$。
  • 否则若 $a_i = b_j$，则必定不满足条件。
• 最后若 $j = |b|$ 则满足，否则不满足。

正确性显然。那么我们直接设 $f_{a, b, c, d, x, y}$ 表示目前 L、I、F、E 的数量分别为 $a, b, c, d$，对于 IF 的指针为 $x$，对于 LIE 的指针为 $y$ 时的答案，最后输出 $f_{A, B, C, D, 2, 3}$ 即可。

时间复杂度：$\mathcal O(ABCD)$。

期望得分：$20$。

算法 3

我会剪枝！

假设 $A, B, C, D$​ 同阶，上面的 DP 只有平方级别的状态是会被转移到的，所以做一下记忆化，只枚举有用的状态就可以通过。具体原因后面会解释。但是由于这个做法常数比较大（需要精细实现才能规避掉哈希表），所以只开了 $A \le 500$。可能存在的小常数立方做法可能也可以通过。

时间复杂度：$\mathcal O(A^2)$（或 $\mathcal{O}(A^3)$）。

期望得分：$40$。

算法 4

我会观察形态！

• 根据上面的判断方式，只考虑 I、F 时字符串应当形如“一段 F，IF，一段 I”的形式，其中首尾这两段都可以为空。
• 只考虑 L、I、E 时字符串应当形如“一段 I/E，L，一段 E、I、一段 L、E、一段 L/I”的形式，其中每一个段都可以为空。

将两者结合起来，根据只考虑 L、I、E 时字符串第一段是否存在 I 可以讨论出四种情况：

• 字符串形如“一段 F/E，L，一段 F/E、I、一段 L、E、一段 L、F、一段 L/I”的形式，其中每一个段都可以为空。
• 字符串形如“一段 F/E，L，一段 F/E、I、一段 L、F、一段 L、E、一段 L/I”的形式，其中每一个段都可以为空。
• 字符串形如“一段 F/E，I，一段 E、L、一段 E、F、一段 E、I、一段 L、E、一段 L/I”的形式，其中每一个段都可以为空。
• 字符串形如“一段 F/E，I，一段 E、F、一段 I/E、L、一段 E、I、一段 L、E、一段 L/I”的形式，其中每一个段都可以为空。

发现这四种情况的每个前缀都只有最多两种字母不是“要么几乎没填过，要么几乎全填上了”的状态，所以前面 DP 的有效状态数就是平方级别的。

前两种情况显然是等价的，算出来第一种之后对答案乘以二即可。

对于这两种情况的单个 I 的位置，显然它已经固定了，由于除了右边单个 E 和单个 F，其他的 E 和 F 都在其左边；除了左边的单个 L，其他的 L 和 I 都在其右边，于是这个 I 的位置就是 $C + D$，而它左右两边互不干涉。它的左边是 $C - 1$ 个 F、一个 L、$D - 1$ 个 E 任意排列的结果，方案数为 $\frac{(C + D - 1)!}{(C - 1)!(D - 1)!}$；它的右边是 $A - 1$ 个 L、一个 F、一个 E、$B - 1$ 个 I 任意排列的结果，并且要求 E 在 F 之前，F 在所有 I 之前，那我们可以将其看作 $A - 1$ 个 L 与 $B + 1$ 个 I 任意排列，并将前两个 I 分别替换成 E 和 F，方案数为 $\binom{A + B}{A - 1}$，两边乘起来再乘上 $2$ 即可。

对于 $B = 1$ 的特殊性质，后两种情况是不可能出现的，所以只需要分析到这里就可以获得对应分数。

对于第三种情况的分析也是类似的，方案数为 $\binom{C + D + 1}{D - 1} \binom{A + B - 2}{A - 1}$。

最后一种情况比较特殊，它没有前三种情况这么好的性质，所以我们直接枚举中间那个 I/E 段中 I 的个数 $i$（$0 \le i \le B - 2$），即可确定后面那个单个 I 的位置为 $C + D + i + 2$，它左右两边互不干涉。它的左边是 $D - 1$ 个 E 与剩下的东西归并起来的结果，方案数为 $\binom{C + D + i + 1}{D - 1}$；它的右边是 $A - 1$ 个 L 与剩下的东西归并起来的结果，方案数为 $\binom{A + B - i - 2}{A - 1}$。

那么我们就算完了所有情况的答案，瓶颈在最后一种情况的枚举。

时间复杂度：$\mathcal O(\sum B)$。

期望得分：$100$。