A · All Closed：中文题面与个人代码

时限 1 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

给定 $n$ 个非空集合 $S_1,\ldots,S_n$ ，每个集合由互不相同的 $m$ 位非负整数组成。一次操作选择 $0\le x<2^m$ ，把 $x$ 同时加入所有集合；某个集合已经含有 $x$ 时保持不变。允许不操作。

若集合 $S$ 中任意两个元素 $x,y$ 都满足 $x\oplus y\in S$ ，则称它对异或封闭。求使所有集合都对异或封闭的最少操作数，并构造任意一种最优操作序列。这里允许 $x=y$ ，所以非空封闭集合必须含有 $0$ 。

输入、输出与约束 #

首行输入 $n,m$ ，其中 $1\le n\le2\times10^5$ ， $1\le m\le20$ 。随后 $n$ 行，每行先给出 $c_i\ge1$ ，再给出该集合的 $c_i$ 个不同元素 $0\le a_{i,j}<2^m$ ；保证 $\sum c_i\le10^6$ 。

第一行输出最少操作数 $k$ ，第二行输出所选的 $k$ 个整数。答案不唯一； $k=0$ 时没有操作元素需要输出。

样例 #

输入 1 #

3 3
1 1
3 0 1 7
6 1 2 3 4 5 7

输出 1 #

3
0 7 6

输入 2 #

1 4
4 11 5 14 0

输出 2 #

样例说明 #

第一组选择 $0,7,6$ 后，前两个集合都变成 $\{0,1,6,7\}$ ，第三个变成 $\{0,1,\ldots,7\}$ ，最少需要三次操作。输出中操作次序可以改变。第二组的集合 $\{11,5,14,0\}$ 已封闭，答案为零。

个人代码：线性基尝试与已定位错误 #

把 $m$ 位整数视为 $\mathbb F_2^m$ 中的向量，非空异或封闭集合正是线性子空间。关键在于一次添加会作用于所有集合，因此不能只分别求每个集合缺失的异或和。

代码的 p[i][j] 是第 $i$ 个集合的线性基，cnt[i] 是秩；c 收集非零基向量，b 把集合元素改写为相对该基的坐标。随后从高位向低位，用 cnt2 统计当前坐标出现情况，寻找缺失坐标 vvv，还原为整数 vv 后放入公共线性基 p[n+1]。最后枚举公共基的所有组合，用 vis 标记，再用 cnt2 删除原本就同时存在于全部集合的元素。

这是原稿的实现路径，尚不能据此给出正确性证明。第一组样例已经有实质性反例：原稿最后只输出两次操作 $0,6$ 。此时第一组集合为 $\{0,1,6\}$ ，但 $1\oplus6=7$ 不在其中，连可行性都不满足。需要加入的新元素会在其他集合中产生新的闭包要求，原稿没有正确完成这一传播。

此外，printf("!!!:%d\\n", i)、打印 b 的循环以及打印 vv,vvv 的语句都会污染标准输出。即使删去这些调试语句，上面的样例反例仍然存在。最小边界输入 1 1 / 1 0 本应直接给出零次操作，原稿仍先打印 !!!:1。

设每组秩为 $r_i$ ，按可见循环可给出保守时间上界 $O(m\sum c_i+\sum_i2^{r_i}+m2^m)$ ，空间 $O(nm+\sum c_i+2^m)$ 。这个上界和实现路径都不代表它已符合时限或得到正确算法。

本地结果： C++17 编译成功；两组样例均被调试输出破坏，第一组还存在上述错误操作集。后续修复必须用闭包合法性和最优操作数检查器验证，不能只比较操作顺序。

原始 C++ 文件 #

下载 A.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：35ffd7fc94adc39cea28c200a9927e58bf350fcc2d34ab19aba48c0e763d8988。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>a[N],b,pm,c;
int p[N][20],n,m,cnt[N],ct[25],vis[1<<20],cnt2[1<<20];
void insert(int s, int x)
{
	for(int i=m-1;i>=0;i--)
	{
		if(!(x>>i))continue;
		if(!p[s][i]){
			p[s][i]=x;
			cnt[s]++;
			break;
		}
		x^=p[s][i];
	}
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,C,v;i<=n;i++)
	{
		scanf("%d",&C);
		for(int j=1;j<=C;j++)
		{
			scanf("%d",&v);
			a[i].push_back(v);
//			cnt2[v]++;
			insert(i,v);
		}
		for(int j=0;j<m;j++)ct[j]=0;
		b.clear();
		c.clear();
		for(int j=0;j<m;j++)
			if(p[i][j])c.push_back(p[i][j]);
		for(int v:a[i])
		{
			int vv=0,ctt=cnt[i];
			for(int j=m-1;j>=0;j--)
			{
				if(p[i][j])ctt--;
				if(!(v>>j))continue;
				v^=p[i][j];
				vv+=(1<<ctt);
			}
			b.push_back(vv);
		}
		printf("!!!:%d\n",i);
		for(int v:b)printf("%d ",v);
		puts("");
		for(int j=cnt[i]-1;j>=0;j--)
		{
			int er=(1<<j)-1;
			for(int v:b)if(v&(1<<j))cnt2[v&er]++;
			int vvv=(1<<j),vv=0;
//			cout<<cnt2[0]<<' '<<cnt2[1]<<'\n';
			for(int k=0;k<=er;k++)
				if(!cnt2[k])
				{
					vvv|=k;
					break;
				}
			if(vvv==(1<<j))
			{
				for(int v:b)if(v&(1<<j))cnt2[v&er]--;
				continue;
			}
			for(int k=0;k<=j;k++)
				if(vvv&(1<<k))vv^=c[k];
			printf("%d %d\n",vv,vvv);
			insert(n+1,vv);
			for(int v:b)if(v&(1<<j))cnt2[v&er]--;
			for(int k=0;k<C;k++)if(b[k]&(1<<j))b[k]^=vvv;
			
		}
//		puts("");
	}
	for(int j=0;j<m;j++)
		if(p[n+1][j])pm.push_back(p[n+1][j]);
	for(int s=0,er=(1<<pm.size());s<er;s++)
	{
		int val=0;
		for(int j=0;j<pm.size();j++)
			if((s>>j)&1)val^=pm[j];
		vis[val]=1;
	}
	int ans=0;
	memset(cnt2,0,sizeof(cnt2));
	for(int i=1;i<=n;i++)
		for(int v:a[i])
			cnt2[v]++;
	for(int i=0;i<(1<<m);i++)
		if(vis[i]&&cnt2[i]==n)
		{
			vis[i]=0;
		}
	for(int i=0;i<(1<<m);i++)
		ans+=vis[i];
	printf("%d\n",ans);
	for(int i=0;i<(1<<m);i++)
		if(vis[i])
			printf("%d ",i);
	return 0;
}