【AGC035C】Skolem XOR Tree

题目

题目链接：https://atcoder.jp/contests/agc035/tasks/agc035_c

• 给定一个正整数 (N)。
• 试判断，是否存在这样一棵节点数为 (2N) 的树，满足：
  • (forall i in [1,n])，第 (i) 号节点和第 (i+n) 号节点的权值均为 (i)。
  • 第 (i) 号节点到第 (i+N) 号节点路径上的点的点权异或和恰为 (i)。
• 若不存在这样的树，请输出一行 No。
• 否则先输出一行 Yes，然后再输出 (2N-1) 行，每行两个正整数 (u,v) 描述树上的一条连接 (u,v) 的边。
• (1 leq N leq 10^5)。

思路

对于一个偶数 (x)，有 (x ext{ xor }(x+1)=1)。考虑连边 ((1,x),(1,x+1),(x,x+1+n),(x+1,x+n))。这样从 (x) 到 (x+n) 的路径，以及从 (x+1) 到 (x+1+n) 的路径，都是符合要求的。
然后考虑点 (1) 应该如何匹配。观察到 (1 ext{ xor }2 ext{ xor }3=0)，所以可以连边 ((1,2),(2,3),(3,1+n),(1+n,2+n),(2+n,3+n))。
然后当 (n) 是偶数时，无法像刚刚那样利用 (n+1) 来进行匹配。那么：

• 如果 (n=2^k)，那么除了 (n) 和 (2n) 以外，所有数在二进制下第 (k) 位都为 (0)，那么一定无解。
• 如果 (n eq 2^k)，只需要找到一组 (x,y)，满足 (x ext{ xor } y ext{ xor }1=n)，然后连边 ((x,n),(y,2n)) 即可。注意 (x) 和 (y) 都不能为 (3) 且必须小于 (n)。容易发现是一定存在这样的 (x,y) 的。

代码

#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
	scanf("%d",&n);
	for (int i=0;i<=18;i++)
		if (n==(1<<i)) return printf("No"),0;
	printf("Yes
1 2
2 3
3 %d
%d %d
%d %d
",n+1,n+1,n+2,n+2,n+3);
	for (int i=4;i<n;i+=2)
		printf("1 %d
1 %d
%d %d
%d %d
",i,i+1,i,i+1+n,i+1,i+n);
	if (!(n&1))
		for (int i=2;i<n;i++)
			if (i!=3 && (n^1^i)!=3 && (n^1^i)<n)
				return printf("%d %d
%d %d
",n,i,n*2,n^1^i),0;
	return 0;
}