Day1-T1 格雷码

格雷码是一种特殊的 \(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;
}