[CSP-S 2019] 格雷码

知识点

二进制、位运算、格雷码

解题思路

本题反射二进制格雷码的第k项等于k xor (k右移1位)。使用unsigned long long保存k和结果，随后从第n-1位到第0位输出每一位。逐位输出能保留前导零，也避免构造2^64造成溢出。

正确性说明

设k的二进制位为b_i，最高位之外补0。公式得到的第i位为b_(i+1) xor b_i。最高位把序列分为前半段0前缀与后半段1前缀；在后半段去掉最高位后，低位的异或值恰等于将编号反射后的低n-1位格雷码。因此该公式满足题目递归构造的初始情形和两半反射规则，归纳可知它正是题目指定的排列。

易错点

k可达到2^64-1，不能用有符号long long；不能计算1ULL<<64；逐位循环的最大位移是63；必须恰好输出n位并保留前导零。

复杂度

时间O(n)，额外空间O(1)，直接逐位输出。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;unsigned long long k;cin>>n>>k;
    unsigned long long g=k^(k>>1);
    for(int i=n-1;i>=0;--i) cout<<((g>>i)&1ULL);
    cout<<'\n';
    return 0;
}