题解：P11613 [PA 2016] 覆盖 / Pokrycia

· · 题解

本文同步发表于 cnblogs。

好牛的一道题目！

首先考虑把最小点覆盖转化为最大独立集，即求出点数为 n 最大独立集为 n-m 的图有多少个，然后预处理出所有可能的 (n,m) 的答案，并 O(1) 回答询问。

本题的关键显然是模数为 2，我们要尝试利用这一性质。

设 N(x) 表示 x 的邻域，如果 N(1) \backslash 2\ne N(2)\backslash1，即点 1 和 2 连向外部的点的集合不一样，那么交换 1 和 2 这两个点会形成一张新的图，且这两张图答案一样，所以这种情况下的答案一定是偶数，不用考虑。于是只需要计算 N(1) \backslash 2= N(2)\backslash1 的情况。

我们按照 1 和 2 之间有没有连边分成两种情况：

这样子两个点都可以变成一个点，我们给每个点赋一个权重，表示这个点是由多少个点合并起来的，初始都为 1。我们按照这样的方式类似的处理 (3,4),(5,6)\ldots，就会有很多权重为 2 的点，然后两个权重为 2 的点又可以继续合并，就可以一直合并下去了（每次合并的两个点要求权重相同，且领域也相同）。

最后会有若干个权重为 2 的幂的点，假设从小到大分别为 2^{a_1},2^{a_2}\ldots 2^{a_l}，并设 m = \sum2^{a_i}。根据前面的性质，一定有 a_i 互不相同（要不然可以继续合并），每个点包含的所有点之间都没有连边（没边才能合并）。

我们设 f(n,m) 表示 n 个点最后变成二进制状态为 m 的方案数有多少种，设 g(n,m) 表示点数为 n 最大独立集为 m 的图的个数。把问题分成两个部分，一是求出 f(n,m)，二是求出一个 f(n,m) 能转移到哪些 g(n,k)。先看第二个部分。

现在已知一个二进制状态 m，我们要确定在这个图上任意连边，对于每个 k，有多少个图的最大独立集为 k。

假设最终的独立集大小为 k，那么 k 的每个二进制位一定是 a_i 里面的，要不然这些点凑不出来。

假如现在给你了一张图和里面的连边，要求出最大独立集。因为每一个点权重都是 2 的幂，于是有个贪心的思路，即从大到小枚举点，如果能选这个点就选，这样一定是最优的。

我们设点 x 表示最大独立集中最大的没有被选择的点，最小的点为 a_1：

所以只有在 k=m 或 k=m-\operatorname{lowbit}(m) 时图的数量为奇数，其余都是偶数。所以一个 f(n,m) 只能转移到 g(n,m) 和 g(n,m-\operatorname{lowbit}(m))。

接下来再看怎么求 f(n,m)。考虑在二进制状态 m 下新加入一个数可以怎么转移。此时新加入一个权重为 1 的点，如果 m 中有权重为 1 的点，那么可以合并或者删去这个点。如果选择合并，就继续看 m 中是否有权重为 2 的点，如果有就还是可以选择合并或者删去。一直做下去，直到 m 中没有权重重复的点，那么有两种结束情况，可能是合并到没法合并了，或者是合并到中途把点删去了。

设 x=\operatorname{lowbit}(m)，考虑这个权重为 x 个点上一步是怎么来的：

于是这道题就做完了，总的来说就是两个转移：

f(n,m) = f(n-1,m-1)+f(n-1,m+\operatorname{lowbit}(m)-1) \\ f(n,m)\rarr g(n,m),f(n,m)\rarr g(n,m-\operatorname{lowbit}(m))

直接做即可，时间复杂度 \mathcal{O}(n^2)。然后这题直接开 bool 数组空间要爆，可以使用 bitset。

#include <iostream>
#include <cstdio>
#include <bitset>
#define ll long long
using namespace std;
const int N = 1<<14;
bitset<N> f[N],g[N];
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    f[0][0] = 1;
    for(int i = 1;i < N;i++)for(int j = 1;j <= i;j++)
    {
        int k = j&-j;
        f[i][j] = f[i-1][j-1]^f[i-1][j+k-1];
        if(f[i][j])g[i].flip(j),g[i].flip(j-k);
    }
    for(int t = rd();t--;)
    {int n = rd(),m = rd();printf("%d\n",(int)g[n][n-m]);}
    return 0;
}

最后，至于为什么要把最小点覆盖转化为最大独立集，原因是最小点覆盖在删去一个点的时候还会让答案 +1，而且最大独立集看起来转移式子更好推一点，当然直接当成最小点覆盖做应该也是可以的。