P11613 [PA 2016] 覆盖 / Pokrycia 题解

是人类能做的题吗，，，感谢 gpt 姐姐帮我理解这个题。

题目就是统计有多少张 $n$ 个点的，最小点覆盖恰好为 $k$ 的有标号简单无向图，答案对 $2$ 取模。

有经典结论：任意 $n$ 个点的无向图中最小点覆盖大小和最大独立集大小的和为 $n$ 。因此问题等价于统计最大独立及大小恰好为 $n-k$ 的图的数量 $\bmod\ 2$ 。

考虑从 $\bmod\ 2$ 这个条件入手。如果能够把满足条件的图两两配对，而且每一对中两个图的最大独立集大小相同，那么这一对点的贡献在 $\bmod\ 2$ 意义下就是 $0$ ，可以直接忽略。

先考虑原图中的 $u,v$ 两个点，此时每个点都只是一个普通的顶点，暂时先给每个点都赋一个权值 $1$ 。点 $u$ 的权值表示选择这个点进入独立集，相当于选择了多少个原始顶点。比较 $u,v$ 两个点向其他点的连边，如果 $u,v$ 两个点对外的邻接情况不同即 $N(u)\backslash\lbrace v\rbrace\neq N(v)\backslash \lbrace u\rbrace$ 则交换 $u,v$ 的所有对外的连边就可以得到一张完全不同的图，此时如果再交换一次就会得到原图。而因为 $u,v$ 两个点的权值相同，因此这样交换相当于是交换了两个等价的位置，因此最大独立集的大小不会改变。此时这两个图全部两两抵消。

因此此时只需要考虑 $N(u)\backslash \lbrace v\rbrace=N(v)\backslash\lbrace u\rbrace$ 的点对 $(u,v)$ （即 $u,v$ 两个点对其他点的邻接情况完全相同）。这个时候剩下 $u,v$ 之间有没有边需要考虑。直接分类讨论：

若 $u,v$ 两个点之间有边则她们不能同时出现在一个独立集中，又因为她们对外完全相同所以选择 $u,v$ 两个点完全没有区别，可以直接删除其中一个点。此时原来两个权值为 $1$ 的点就变成了一个权值为 $1$ 的点。
若 $u,v$ 两个点之间没有边，则因为其对外邻接情况完全相同，所以如果一个最大独立集选择了 $u$ 点但是没选择 $v$ 点，则 $v$ 点和 $u$ 点的邻居必然完全一样，但是 $v$ 点却和 $u$ 点没有边，所以一定可以把 $v$ 点加入到最大独立集中。因此这类情况的 $u,v$ 在最大独立集中要么都被选要么都不被选。因此此时 $u,v$ 两个点可以被合并为一个大点，这个大点的权值被设为 $2$ 。

然后考虑继续仿照上述操作进行合并所有的大点并继续配对得到权值更大的大点，以此类推直到无法合并当前最高级的大点为止。显然处理完后所有的大点的权值一定都是 $2$ 的幂次，而且每种权值最多存在一个点，因为如果还剩下两个相同权值的点则还可以继续进行上面的操作。

用一个二进制编码来表示最终状态，该编码可以看作是将图中最后剩下的所有点的权值相加得到的值。容易证明一个二进制编码对应唯一一组大点权值的集合。

考虑 dp。设 $f_{i,j}$ 表示从 $i$ 个原始点出发，经过上面的配对合并和删除后，最终得到状态 $j$ 的图数量对 $2$ 取模后的结果。考虑怎么从 $i-1$ 个点的情况转移到 $i$ 个点的情况。新加入的点初始权值一定为 $1$ ，假设最终想要得到的状态是 $S$ ，记 $w$ 是 $S$ 二进制表示中最低的 $1$ 为止对应的权值，则这个新点有两种不同的阶举：一种是新的点一路合并最后被在状态 $S$ 中，为了得到最后的状态 $S$ 加入新点前的状态必须是 $S-1$ ，加入权值为 $1$ 的新点之后低位连续发生合并，最后形成了 $S$ 中最低的大点。另一种情况是新点一路合并到权值 $w$ 然后被删除，这个情况需要满足原状态中所有低于 $w$ 的权值都存在而且本来已经包含一个权值为 $w$ 的大点，因此原状态为 $S+w-1$ 。

因此 dp 转移式形如： $f_{i,S}=f_{i-1,S-1}\oplus f_{i-1,S+\operatorname{lowbit}(S)-1}$ 。

初始状态显然就是 $f_{0,0}=1$ 。

然后考虑固定最终的大点组成的集合后，她们之间互相连边可以产生怎样的最大独立及大小。因为所有大点的权值都是互不相同的 $2$ 的幂次时一个大点的权值一定严格大于所有权值比她小的大点的权值的和，因此求最大全独立集的时候可以按照权值从大到小贪心处理，如果当前大点和所有已经选择了的权值更大的大点互不冲突则一定应该选择她，因此最大独立集可以被唯一的由这个贪心算法刻画而来。

先考虑如果所有大点都被选中到最大独立集中的情况，此时所有大点之间都必须没有任何边，对答案的贡献就是 $1$ 。

然后再考虑只有最小权值的大点没有被选中到最大独立集中的情况。此时除了这个大点以外其余点都被选择，因此其余大点之间都不能有边相连。而最小值的大点想要不被选择就必须和至少一个其余被选中的点之间有边相连。如果共有 $m$ 个大点，则权值最小的大点向其余 $m-1$ 个大点的非空连边方式共有 $2^{m-1}-1$ 种，是奇数，因此会对最大独立集大小贡献 $1$ 。

然后考虑如果还有其他大点没有被选中到最大独立集中的情况。则此时她在贪心的过程中必然和某个权值更大的大点有边相连。此时翻转她和和她相连的最小的超级点的边不会改变贪心得到的最大独立集，因此这些图可以再次两两配对，模 $2$ 后不会对答案产生任何贡献。

因此对一个状态 $S$ 而言其在 $\bmod\ 2$ 意义下只会贡献两个独立集大小，分别是 $S$ 和 $S-\operatorname{lowbit}(S)$ ，对答案的贡献都是 $1$ 。因此考虑再次 dp，设 $g_{i,j}$ 表示当前考虑 $i$ 个点对图，最大独立集大小恰好为 $j$ 的图的数量对 $2$ 取模后的结果。如果当前 $f_{n,S}=1$ 则因为 $S$ 这个状态恰好等价于其对应的最大独立集的大小，因此直接转移 $g_{n,S}\leftarrow g_{n,S}\oplus 1$ 即可。

然后第二个贡献 $S-\operatorname{lowbit}(S)$ 需要先保证 $S$ 本身不是 $2$ 的幂次即本身不止有一个大点才可以转移，如果可以转移的话直接转移 $g_{n,S-\operatorname{lowbit}(S)}\leftarrow g_{n,S-\operatorname{lowbit}(S)}\oplus 1$ 即可。

预处理出 $f,g$ 两个数组的信息，然后对一组查询 $(n,k)$ 答案就是 $g_{n,n-k}$ 的值。预处理部分的时间复杂度为 $O(n^2)$ ，空间复杂度可以拿 bitset 优化一下做到 $O(n^2/w)$ ，可以通过该题。

:::success[Code]

namespace lowspeed_song {

bitset<(1 << 14)> f[1 << 14], g[1 << 14];

inline void init() {
    f[0][0] = 1;
    for (int i = 1; i < (1 << 14); ++i)
        for (int j = 1; j <= i; ++j) {
            f[i][j] = f[i - 1][j - 1] ^ f[i - 1][j + (j &- j) - 1];
            if (f[i][j]) {
                g[i][j].flip();
                if (j != (j &- j)) g[i][j - (j &- j)].flip();
            }
        }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, k; cin >> n >> k;
    cout << g[n][n - k] << '\n';
}

} // namespace lowspeed_song

:::

隐藏／恢复文章

随机文章