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}\backslash displaystyle\; T\; \backslash subseteq\; \backslash bigcup\_\{k=1\}^i$ ，即由 $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$ 。

这个问题显然可以使用子集DP解决，但子集DP的时间复杂度是 $O(3^n)O(3^n)$，在 $n=20n=20$ 时无法通过。

考虑优化转移，我们将输入视为二进制，从小到大枚举每个输入的集合，并实时记录最高位，这样就可以只枚举其补集比其小的子集转移，可以通过。

统计答案时，使用高维后缀min维护答案。

#include<cstdio>
#include<algorithm>
#define min(_,__) (_<__?_:__)
bool w[1200200];
int n,k,f[1200200],v,ans[30],a[101010],lo[1101010],g[1200200];
int main(){
	scanf("%d%d",&n,&k);v=1<<k;--v;
	for (int i=1;i<=v;++i) f[i]=k+1;
	lo[1]=1;
	for (int i=2;i<=v;++i) lo[i]=lo[i>>1]<<1;
	int x,m,e;
	for (int i=0;i<n;++i) {
		scanf("%d",&m),x=0;
		while (m--) scanf("%d",&e),x|=1<<e-1;
		a[i]=x;
	}
	std::sort(a,a+n);
	v=1;
	for (int i=0;i<n;++i) {
		while (v+1<lo[a[i]]) v=(v<<1)^1;
		while (a[i]==a[i+1]) ++i;
		for (int j=a[i];j;j=j-1&a[i]) f[j]=1;
		x=v&~a[i];
		for (int j=x;j;j=j-1&x) f[j|a[i]]=min(f[j|a[i]],f[j]+f[a[i]]);
	}
  	--n;
	v=1<<k;--v;
    for (int i=1;i<v;++i) f[i|a[n]]=min(f[i|a[n]],f[i]+1);
	for (int i=v;i;--i) {
		for (int j=1;j<v;j<<=1) if (i&j) f[i^j]=min(f[i],f[i^j]);
		++ans[f[i]];
	}
	for (int i=1;i<=k;++i) printf("%d ",ans[i]);
	
	return 0;
}