题目传送门
正解
思路
n 的特殊值:
\(n=0\)
- 此时,只有一个数,所以 k 是多少并不能对它造成限制,直接输出即可。
\(n=1\)
- 此时,有两个数,且这两个数是 0 和 1 ,所以 k 只能等于 1 。
此后,不妨假设 \(n \ge 2\)
无解情况
事实上,它有解当且仅当 \(n>k\) 且 \(k \mod 2 =1\) (也就是 k 为奇数)。
证明:
对于 \(n>k\)
-
显然, \(n<k\) 无解很好理解
-
但是 \(n=k\) 的时候,为什么无解呢?
-
这个其实也好理解,因为如果 \(n=k\) ,就要求相邻两个元素完全取反,所以这种情况合法当且仅当 \(n=1\) ,而现在已经假设了 \(n \ge 2\) ,所以它无解
-
为什么成立了就有解呢?这个其实也不一定,它只作为其中一个限制条件,剩下的看下面。
对于 \(k \mod 2 =1\)
-
如果 k 为偶数,不难发现,每两个数之间的 \(popcount\) 一定相差偶数个,即奇偶性相同,这时候,只能保证出现所有 \(popcount\) 奇偶性相同的数,对于不同的数则不可能出现,然后就 GG 了。
-
反之,则可以一奇一偶交替覆盖,便有解了。
如何构造
这里,不妨先假设 \(n=k+1\)
然后怎么做呢?
Step 1
-
首先,构造一个格雷码 \(a_1\sim a_{...} \sim a_{2^n}\)
-
怎么构造呢?很简单:
a[i]=i^(i>>1)
-
为什么?我也不知道 QWQ
-
反正它对就是了~
Step 2
- 注意到,格雷码中每两位之间有且仅有一位不同,即 \(n-1\) 位相同,将每一个下标为偶数的元素取反 ( \(\oplus 2^n-1\) ),就变成了 \(n-1\) 位不同,而我们已经假设 \(n=k+1\) ,所以此时任意两位之间都有 \(k\) 位不同,符合题意。
Step 3
-
对于每个 \(a_i\) ,将其 \(\oplus 2^n+2^{k-1}-1\) ,得到 \(c_1 \sim c_{...} \sim c_{2^n}\),其中, \(2^n\) 意味着最高位的取反,而 \(2^{k-1}-1\) 则意味着最后 \(k-1\) 位的取反,这样,刚好有 \(k\) 位变得相反。
-
然后,把每个 \(c_i\) 倒序拼到 a 序列的后面,得到的就是 n 再增大 1 的答案。
-
正确性:
-
首先,c 序列只是将最后 \(k-1\) 位取反,这意味着该覆盖到的还是覆盖到了。
-
其次,c 序列将最高位取反,这意味着它覆盖了 n 再增大 1 的答案的另一部分,保证了不重不漏地覆盖每一个数。
-
然后,不断按照此操作进行覆盖,直到 \(n\) 符合数据要求即可。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,now;
int a[3050000],c[3050000];
int main(){
scanf("%d%d",&n,&k);
if(n==0){printf("1\n0\n");return 0;}
if(n==1){if(k==1) printf("1\n0 1\n");else printf("0\n");return 0;}
if(k>=n||!(k&1)){printf("0\n");return 0; }
printf("1\n");
now=k+1;
for(int i=0;i<(1<<now);++i) a[i]=i^(i>>1);//格雷码公式
for(int i=0;i<(1<<now);++i,++i) a[i]^=((1<<now)-1);//将偶数位取反
for(;now<=n;++now){
for(int i=0;i<(1<<now);++i)
c[i]=a[i]^((1<<now)+(1<<(k-1))-1);//按照上面进行取反
for(int i=0;i<(1<<now);++i)
a[(1<<now)+i]=c[(1<<now)-i-1];//倒序拼接
}
for(int i=0;i<(1<<n);++i)
printf("%d ",a[i]);
printf("\n");
return 0;
}