更好的阅读体验

Statement

格雷码是一种特殊的 $n$ 位二进制串排列法，要求相邻的两个二进制串恰好有一位不同，环状相邻。

生成方法：

1. $1$ 位格雷码由两个 $1$ 位的二进制串组成，顺序为 $0,1$
2. $n+1$ 位的格雷码的前 $2^n$ 个串，是由 $n$ 位格雷码顺序排列再加前缀 0 组成。
3. 后 $2^n$ 个串，由 $n$ 位格雷码逆序排列加前缀 1 组成。

求 $n$ 位格雷码的第 $k$ 个串。

$1\leq n\leq 64,0\leq k\leq 2^n$ .

Thoughts & Solution

考虑一个跟康托展开非常相似的思路。

首先看第一位，如果是 1 那么说明它前面已经可以确定至少排了 $2^n$ 个 0 开头的二进制串。

那么这样就可以确定第一位是 0 还是 1 ，看 $k$ 的大小就好了。

后面的也是同理，每次判断完之后：

• 如果是 1 就把 $k$ 减去 $2^i$ ，然后由于这一位是 1 ，所以后面的都需要逆序，直接用总个数减去减完之后的 $k$ （注意，这个逆序是相对于下一层而言的，所以应该是 $2^i-(k-2^i)-1$ ，也就是 $2^{i+1}-k-1$）
• 不是 1 ，就不动，给出 0 ，然后继续下一位即可。

复杂度是 $\mathcal{O}(n)$ 的。（不过这种题也不需要考虑这个吧）

最后：经过 CSP-S2020 ，我发现 $k<2^n\leq 2^{64}$ （

写代码的时候注意溢出问题，要开 unsigned long long 特别是左移的地方要注意。

//Author: RingweEH
#define ull unsigned long long
const int N=70;
int n,a[N];
ull k;

int main()
{
    n=read(); scanf( "%llu",&k );

    ull now=1ull<<(n-1);
    for ( int i=n-1; i>=0; i-- )
    {
        if ( (k>>i)&1 ) a[i]=1,k=(now<<1)-k-1;
        else a[i]=0;
    }

    for ( int i=n-1; i>=0; i-- )
        printf( "%d",a[i] );

    return 0;
}