ABC366 G - XOR Neighbors 题解

发现题目实质上就是让你构造一组 \(a_{1,2,\dots,n}\)，有一些限制，要求一些 \(a\) 异或起来是 \(0\)。

看到 \(n\le 60\)，果断列异或方程组，用异或高斯消元。

具体地，有 \(n\) 个方程组，\(a_{i,j}\) 表示第 \(i\) 个方程中 \(j\) 的系数。对于每一个变量 \(i\)，要把 \(j>i\) 的方程中的第 \(i\) 项用第 \(i\) 个方程异或起来消掉（如果 \(a_{i,i}=0\) 就把一个 \(a_{j,i}\ne 0\) 且 \(j>i\) 的方程和第 \(i\) 个方程交换），因为等号右边是 \(0\) 所以可以不用处理。

从后往前构造解，如果 \(a_{i,i}=0\)，这是可能的，那么就令 \(ans_{i}=2^i-1\)；否则，就令 \(ans_i=\bigoplus_{j>i} ans_j\times a_{i,j}\)。

后一点比较容易理解，前一点不太容易理解，我认为这样子填 \(ans_i\) 的话对于 \(j<i\) 的 \(ans_j\) 的第 \(i\) 位反映的是 \(ans_i\) 对 \(ans_j\) 是否有影响，如果 \(ans_j=0\)，\(ans_j\) 的第 \(i\) 位一定是 \(0\)，这样子 \(ans_i\) 对 \(ans_j\) 没有影响，这样子 \(ans_j\) 是 \(0\) 这件事就和 \(ans_i\) 无关的。类似的，可以发现这和每一个填 \(ans_i=2^i-1\) 的 \(ans_i\) 都没有关系，那么只能说明 \(ans_j=0\) 是命中注定的，该局面无解。

事实上有人在 \(a_{i,i}=0\) 时填 rand 也过了。

如果存在一个 \(ans_i=0\)，那么一定无解。

const int N=65;
int n,m,a[N][N]={};
ll ans[N]={};
int main()
{
//	usefile("G");
	int i,j,k,x,y;
	read(n,m);
	for(i=1;i<=m;++i)
		read(x,y),a[x][y]^=1,a[y][x]^=1;
	for(i=1;i<=n;++i) {
		if(!a[i][i]) {
			for(j=i+1;j<=n;++j)
				if(a[j][i]) {
					swap(a[i],a[j]);
					break;
				}
		}
		if(!a[i][i]) continue;
		for(j=i+1;j<=n;++j)
			if(a[j][i]) {
				for(k=1;k<=n;++k)
					a[j][k]^=a[i][k];
			}
	}
	for(i=n;i;--i) {
		if(!a[i][i]) {
			ans[i]=(1ll<<i)-1;
			continue;
		}
		ans[i]=0;
		for(j=i+1;j<=n;++j)
			if(a[i][j])
				ans[i]^=ans[j];
	}
	for(i=1;i<=n;++i)
		if(!ans[i]) {
			printf("No\n");
			return 0;
		}
	printf("Yes\n");
	for(i=1;i<=n;++i)
		printf("%lld ",ans[i]);
	printf("\n");
	return 0;
}