哎呀这个C怎么比B还水。。。。(我现在大概也就会做点这种水题了吧)
题目链接
https://atcoder.jp/contests/agc031/tasks/agc031_c
题目大意
符号约定: (count(x))表示整数(x)在二进制表示下(1)的个数。“二进制表示下第(x)位”表示位权为(2^x)的位。数组下标全部从0开始
给定(N,A,B), 求构造一个([0,2^N-1])的排列(p), 满足(p_0=A, p_{2^N-1}=B), 对于任何(iin[1,2^N-1]), (count(p_i xor p_j)=1).
(1le Nle 17)
题解
注: 这道题“二进制位相差(1)个”的这个条件，我们可以用图形象地表示出来，就是一个(n)维立方体顶点和棱的几何结构。这样画出来也许有助于理解本题。
首先观察到一些结论。
(1) 如果一个排列(p)是合法的，那么把(p)中的每个元素异或一个正整数(x)之后得到排列(p')，排列(p')仍然是合法的。
太显然，不证了。
据此，我们可以令(B=B xor A), 然后构造一个(p)满足(p_0=0, p_{2^N-1}=B), 最后把答案序列全部(xor A)
(2) 能构造出以(0)开始以(B)结束的合法排列当且仅当(count(B)equiv 1(mod 2))
证明: (|count(p_i)-count(p_{i-1})|=1), 故(count(p_{2^N-1}))为奇数。必要性得证。
充分性？我们可以直接按以下方案进行构造
假设我们要解决问题((n,b)) (表示大小为(n)起始点为(0)终止点为(b))
分类讨论(b)二进制表示下第((n-1))位
若为(1), 则我们先在([0,2^{n-1}-1])内构造一个起始点为(0)终止点为(1)的排列(递归调用问题((n-1,1)))，然后从(1)这个点一步跳到(2^{n-1}+1), 再构造一个([2^{n-1},2^n-1])的起始点为(2^{n-1}+1)终止点为(b)的排列。这一部分可以递归调用问题((n-1,b xor (2^{n-1}+1)))然后把生成的排列每个位置都异或(2^{n-1}+1)解决。
若为(0), 情况稍有复杂。我们依然是构造两个排列，第一个排列(p_1)由问题((n-1,a))生成, 而我们希望在排列(p_1)中塞入另一个排列，而使得新排列仍然合法。考虑(p_1[0])和(p_1[1]) (其中(p_1[0])显然为(0)), 构造一个排列(p_2)值域为([2^{n-1},2^n-1])且起始于(2^{n-1})终止于(p_1[1] xor 2^{n-1})，这一部分可以通过调用问题((n-1,p_1[1]))然后给生成排列的每个元素都加上(2^{n-1})完成。然后我们把(p_2)接在(p_1[0])和(p_1[1])之间，它就合法了。
时间复杂度(T(n)=2T(n-1)+O(2^n)), 解得(T(n)=O(2^nn))
说了这么多，可能不太清楚。。后面我举个例子：(仅展开模拟第一层递归)
例子1: 问题(4,13)的解决
判断出为第一种情况(第3位为1)
首先构造问题(3,1)的排列: 0 4 5 7 6 2 3 1
然后构造问题(3,4)的排列: 0 2 3 1 5 7 6 4，其中4=13 xor 9, 9=2^3+1
问题(3,4)的排列每个数xor 9之后可得: 9 11 10 8 12 14 15 13
前后拼接即可得: 0 4 5 7 6 2 3 1 9 11 10 8 12 14 15 13就是答案
例子2: 问题(4,7)的解决
判断出为第二种情况(第3位为0)
首先构造问题(3,7)的排列p1: 0 2 3 1 5 4 6 7, 发现p1[1]是2
然后构造问题(3,2)的排列: 0 4 6 7 5 1 3 2, 然后每个数+8后可得8 12 14 15 13 9 11 10
然后把这个以8开头以10结束的排列插在p1的0和2之间，得到0 8 12 14 15 13 9 11 10 2 3 1 5 4 6 7就是答案
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N = 17;
int ans[(1<<N)+3];
int cnt[(1<<N)+3];
int tmp[(1<<N)+3];
int n,A,B;
void solve(int x,int a,int ret[])
{
if(x==0) {ret[0] = 0; return;}
if(x==1) {ret[0] = 0; ret[1] = 1; return;}
if(a&(1<<(x-1)))
{
solve(x-1,1,ret);
solve(x-1,a^((1<<(x-1))+1),ret+(1<<(x-1)));
for(int i=(1<<(x-1)); i<(1<<x); i++) ret[i] = ret[i]^((1<<(x-1))+1);
}
else
{
solve(x-1,a,ret);
solve(x-1,ret[1],ret+(1<<(x-1)));
for(int i=(1<<(x-1)); i<(1<<x); i++) ret[i] = ret[i]^(1<<(x-1));
tmp[0] = ret[0]; for(int i=0; i<(1<<(x-1)); i++) tmp[i+1] = ret[i+(1<<(x-1))];
for(int i=((1<<(x-1))+1); i<(1<<x); i++) tmp[i] = ret[i-(1<<(x-1))];
for(int i=0; i<(1<<x); i++) ret[i] = tmp[i];
}
}
int main()
{
scanf("%d%d%d",&n,&A,&B); B^=A;
for(int i=1; i<(1<<n); i++) cnt[i] = cnt[i>>1]+(i&1);
if((cnt[B]&1)==0) {puts("NO"); return 0;}
puts("YES");
solve(n,B,ans);
for(int i=0; i<(1<<n); i++) ans[i]^=A;
for(int i=0; i<(1<<n); i++) printf("%d ",ans[i]);
return 0;
}