Perception & Trick | Establish Mapping in Counting Problems

· · 算法·理论

计数题中，建立合法和不合法方案的映射关系，是一个很重要的思想。

可能算是烂大街了，但是仍然有一些巧妙的应用。

注：本文略去了大多数题目的 DP 转移，因为这并不是本文的主要讲解对象。

Problem A P5933

最简单的模型：图上连通性问题计数。

为了方便，在这里先考虑不带权的做法。设 F(S) 表示集合 S 中的点形成连通图的方案数，G(S) 表示形成不连通的方案数，A(S) 表示所有情况，即 2^m（m 为边数）。

有以下性质：

  2. 建立“不连通图”向“连通图”的唯一映射：取出 S 中编号最小的点所在的连通块 T，T \subset S，则构造映射 S \to T。而且还可以建立数量关系：G(S) = \sum F(T)A(S-T)。

然后状压 DP 就做完了。

满足上述性质即可具备使用该 trick 解决问题的条件了。

Problem B QOJ9116

一个前置的字符串知识：如果一个字符串存在长度过半的 border，那么也存在一个不过半的 border。

然后这个就是简单题了。对于一个有 border 的（不合法）串，找到其最短 border，则这个最短串没有 border（合法）。建立映射完成。

令 F(i) 表示长度为 i 的合法串数量，G(i) 表示长度为 i 的不合法串数量。

有 G(i) = \sum \limits_{k\in[1,\frac{i}{2}]} F(i)m^{i-2k}。容易前缀和优化 DP。

Problem C CF1089I

一个排列上连续段相关问题的性质，手推起来十分困难，不过前人已经有了现成的研究结果：析合树。

这里略去析合树的部分（可以自行搜索博客）。

题目要求计数的就是所有形如根为合点，下面挂着 n 个儿子的方案数。

那么考虑计数不合法的：

这种情况的充要条件是任意连续的（多余两个）儿子对应的区间都不是连续段。

将一段值域缩成一个点，惊奇地发现又回到了原问题，但是规模更小，变成了 c。每个儿子内部的排列方案是其大小的阶乘。这样就建立了映射。

钦定最短的是连续段的前缀即可，和 Problem B 差不多。实现的时候可以仅考虑儿子从左到右递增的情况，最后再乘 2。

Problem D P10879

详细题解

其实是有更简单的做法的。以下截取了计算 P(a,b \to c)（即 a,b 的 LCA 为 c 的概率）的部分，这部分用到了本文的思想：

  • 如果钦定 a,b 最后一次相交在 c_0 处，那么计算 Q(x \to y) 表示 x 到 y 走两条不相交路径的概率。但是 Q 本身也只能容斥算了，似乎规约到很复杂的问题，一般来说必须 \mathcal{O}(n^3)。

  • 如果钦定 a,b 第一次相交在 c_0 处，那么 c_0 到 c 的路径就任意了。我们可以很简单地写出转移：

P(a,b \to c) = P(a\to c) \cdot P(b \to c) - \sum_{c_0} P(a,b \to c_0) \cdot P^2(c_0 \to c)

也就是 a,b 先走到 c_0，再各走各路（可以任意相交）走到 c。

Problem E CF1750F

令 F(x) 表示长度为 x 的序列，首尾为 1 且满足题目条件的方案数，G(x) 为不满足，则有 F(x) + G(x) = 2^{x-2}。

然后建立一个映射：考虑一个不合法的序列，将其操作到不能再操作为止，则操作结束后序列唯一。

此时序列形成 1...1|0...0|1...1|0...0|1...1| 的形状，每一段 0 的长度比周围两段 1 长度总和要大。

其中每一段 1 在操作前都是合法序列。

Problem *F CF1605F

先把问题进行转化：记录一个变量 V 初始为 0，不断在序列中找两个数 x,y 使得 x - x \operatorname{and} V = y - y \operatorname{and} V，然后将 x,y 重排在序列两端，然后将是 V 的子集的数去掉（可以放在序列中间），最后只能剩一个数（n 为奇数）或一个都不剩，那么序列就是合法的。

对于不合法的方案，我们可以先不断对其操作，直到不能再操作，即剩余的数 x - x \operatorname{and} V 互不相同且均不为 0，发现操作最终的结果也是唯一的。然后删掉的那部分数其实就是一个合法方案。数量关系也建立了起来。

DP 转移较为复杂。

Problem *G AGC067B

考虑判定。将过程倒过来，贪心选取同色段变成通配符，直到不能选取。会剩下一些字符选不了了。那么变成通配符的就是合法方案，整个串就是不合法方案，映射成立。

目前只收录 7 题（一个校内模拟赛题不能公开），欢迎大家投稿。