2022 年牛客多校第九场 K 题题解

K NIO's OAuth2 Server

题意：有 $kk$ 个元素和 $nn$ 个由这 $kk$ 个元素构成的集合 $\{S_n\}\backslash \{S\_n\backslash \}$，问由这 $kk$ 个元素生成的全部 $2^k-12^k-1$ 个非空集合中有多少个 $TT$ 集合满足 ${\displaystyle T\subseteq \bigcup _{k=1}^i{S}_k}\backslash displaystyle\; T\; \backslash subseteq\; \backslash bigcup\_\{k=1\}^i\; S\_k$，即由 $ii$ 个集合能覆盖 $TT$ 集合，对于 $i\in [1,k]i\; \backslash in\; [1,k]$ 计算答案。$k\le 20k\; \backslash leq\; 20$，$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$。

解法：首先利用状压将显然所用集合个数不会超过 $kk$ 个，因而可以枚举进行 $ii$ 次集合并操作，能得到的集合个数。

这样问题转化为，对这 $nn$ 个集合进行 $ii$ 次任意并操作，能得到哪些集合。那么利用集合幂级数，使用 ${\displaystyle f(x)=\sum _{i=0}^{2^k-1}{f}_i{x}^i}\backslash displaystyle\; f(x)=\backslash sum\_\{i=0\}^\{2^k-1\}f\_ix^i$，其中 $f_{i}f\_i$ 为合成集合 $ii$ 的方案，进行 $ii$ 次 FWTor 即可。最后统计答案的时候，只需要统计系数（方案数）是否为 $00$，若 $f_{i}f\_i$ 不为 $00$ 则表示可以合成，同时对于后面的计算需要强制令 $f_i=1f\_i=1$ 否则最后的方案数可能过大导致溢出。

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
using Poly = vector<long long>;
void FWTor(Poly &a, bool rev)
{
    int n = a.size();
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1)
        for (int j = 0; j < n; j += l)
            for (int i = 0; i < m; i++)
                if (!rev)
                    a[i + j + m] += a[i + j];
                else
                    a[i + j + m] -= a[i + j];
}
Poly operator |(Poly a, Poly b)
{
    int n = a.size();
    FWTor(a, 0), FWTor(b, 0);
    for (int i = 0; i < n; i++)
        a[i] *= b[i];
    FWTor(a, 1);
    return a;
}
int ans[1 << N], cnt[N + 1];
int main()
{
    int n, k, x, z;
    scanf("%d%d", &n, &k);
    Poly base(1 << k, 0), f(1 << k, 0);
    f[0] = 1;
    while(n--)
    {
        int y = 0;
        scanf("%d", &x);
        while(x--)
        {
            scanf("%d", &z);
            y |= 1 << (z - 1);
        }
        base[y] = 1;
    }
    for (int i = 0; i < k; i++)
        for (int j = (1 << k) - 1; j >= 0; j--)
            if (!(j & (1 << i)))
                base[j] += base[j ^ (1 << i)];
    for (int i = 0; i < 1 << k;i++)
        if(base[i])
        {
            base[i] = ans[i] = 1;
            if (i)
                cnt[1]++;
        }
    for (int j = 1; j <= k; j++)
    {
        f = f | base;
        for (int i = 1; i < 1 << k; i++)
            if (f[i] && !ans[i])
            {
                ans[i] = j;
                cnt[j]++;
            }
        for (auto &i : f)
            if (i)
                i = 1;
    }
    for (int i = 1; i <= k;i++)
        printf("%d ", cnt[i]);
    return 0;
}