7.14 小计

Set

给出 \(m\) 个集合，每个集合 \(n\) 位，定义 \(f(T)\) 表示 \(\sum\limits_{i=1}^m[|T \cap S_i|\ge k]\)，对于 \(1\) 到 \(n\)，求满足 \(f(T)\ge i\) 的最小的 \(|T|\)。

神秘题，想到容斥但是不知道系数，学到了 dp 算系数的操作。

具体的，对于每个数 \(x\) 求出它的超集和 \(g(x)\)，然后乘上算出的系数得到 \(x\) 位数的贡献，保证每个数贡献一次后，再求一次子集和便得到了 \(f(T)\)。最后随便求个后缀最小值就是答案。

#include<bits/stdc++.h>
#define ll long long
#define N 25
#define M 300005
using namespace std;
ll C[N][N];
int n,m,k;
ll cf[N];
char t[N];
ll a[(1<<N)+5];
int count(int x){int cur=0;while(x){cur+=x&1;x>>=1;}return cur;}
int res[M];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	for(int i=k;i<=n;i++) //the length of the 1
	{
		ll cur=0;
		for(int j=k;j<i;j++) // the contribution of each length 
			cur+=C[i][j]*cf[j];
		cf[i]=1-cur;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%s",t+1);
		int cur=0;
		for(int j=1;j<=n;j++)
			cur+=(t[j]=='1')*(1<<n-j);
		a[cur]++;
	}
	for(int i=1;i<=n;i++)
		for(int mask=0;mask<(1<<n);mask++)
			if(!(mask&(1<<i-1))) a[mask]+=a[mask^(1<<i-1)];
	for(int mask=0;mask<(1<<n);mask++) a[mask]*=cf[count(mask)];
	for(int i=1;i<=n;i++)
		for(int mask=0;mask<(1<<n);mask++)
			if((mask&(1<<i-1))) a[mask]+=a[mask^(1<<i-1)];
	memset(res,127/3,sizeof res);
	for(int mask=0;mask<(1<<n);mask++) res[a[mask]]=min(res[a[mask]],count(mask));
	for(int i=m-1;i>=1;i--) res[i]=min(res[i],res[i+1]);
	for(int i=1;i<=m;i++) printf("%d\n",res[i]);
	return 0;
}