题解：P11567 建造军营II

Graygoo · 2025-01-12 20:59:43 · 题解

先考虑解决一个和本题正解关联度很大的问题：给定 n 个点与其邻接矩阵，再给出将每个集合看作一个 "节点" 的方案数，要求你求出先将全集拆成一些 "节点"，然后将这些节点连成树的方案数和。(两个 "节点" 之间边的数量还是按照原图这两个集合之间边数量计算)。

我们有一个朴素做法，大概是枚举根的集合，然后再对子树dp，这样的话由于根不同根和子树间边数也不同，必须记录一个 3^n 的状态，加上枚举子集成了 4^n，如果用这玩意来实现本题做法可以过 n=13 的点。可以使用子集卷积优化到 O(3^n \cdot n^2)，没啥用。

考虑更高妙做法。如果我们直接做 f_S \cdot f_T→f_{S+T} 这样一个简单转移，毫无疑问会算重，但是观察一下算重的次数，发现实际上是以"合并操作"为边建立的一个树的拓扑序个数。那么我们只要同时记录 f_{S,v} 表示 S 这个集合由 v 个小集合合并而来，然后一转移好 f_{S,∗} 就把 f_{S,v}→{f_{S,v} \over v} ，自然就把算重的部分给干掉了。这样我们得到一个新的 O(3^n \cdot n^2)，但常数不知道比上面那个小到哪里去了。

继续优化这个做法。发现我们在做子集卷积时同时还要做 (+,×) 卷积，这个非常亏。考虑直接维护点值，需要系数时再插回来就好了。可以预处理拉插的系数。复杂度变为 O(3^n⋅n+2^n \cdot n^2+n^3)。

我们宣称，本题做法就是若干个上述问题（下称 X 问题）的拼接。

首先套路式地发现，一个 (p_i,q_i) 的约束实际上就是从 p_i 所在的边双连通分量到 q_i 所在的边双连通分量之间的所有边都必须有军队驻守。那么我们自然要考虑处理出一个集合是一个边双连通分量情况下的内部连边方案数。那么我们先搞出一个集合是联通的方案数，这个相信大家都会。然后如果这个集合是联通的但不是一个边双，内部的边双就必定组成一棵树，我们利用 X 问题把这种情况容斥掉即可。

随后我们观察最终的边双树的形态，发现实际上是由 未被染色的边双与被染色的极大连通块 构成的树（当然需要约束没有跨越集合的边），这也是一个 X 问题。那么现在我们需要求出每个集合作为"被染色的极大联通块"的方案数。如果这个集合被分为了多个被染色的极大联通块，它们还是形成一棵树，所以我们又可以使用 X 问题容掉它，所以本题就做完了。