題解【luogu 5657グレイコード】

CSP-S2 2019 D1T1
試験場で最初に問題を読んだとき、あまり目立たなかったような気がしますが...D 1 T 1の雰囲気に合わないです
グレイコードが何なのか全く聞いたことがありませんが、やはり私は料理が多すぎます.
問題をよく読んでみると法則があるはずだ.
試合後$O(1)$アルゴリズムがあるそうですが、どうせ私はできません.
構想分析
いくつかの小さな桁数のグレイコードの全配列を書き出して、グレイコードの生成アルゴリズムに基づいて、以下のアルゴリズムがあります.
1.$x$ビットの$k$個目のグレイコードについて、$kgeq 2^{x-1}$の場合、明らかにこのグレイコードは$x-1$ビットの$2^{x-1}-(k-2^{x-1}+1)=2^x-k-1$個のグレイコードの前に1を加えたものである.そうでなければ、このグレイコードは$x-1$ビットの$k$番目のグレイコードの前に0を加えたものである.$x=0$になるまで手順1を繰り返します.
具体的な実装
シミュレーションすれば、シミュレーションしながら出力できます.
データ範囲を見て、わざわざ$5$分の$unsigned$long$long$を提示しました.のだから覚えてる
べき乗を求める時も精度の問題に注意して、高速べき乗を使うことができます

#include
#include
#define ull unsigned long long
using namespace std;
int n;
ull k;
ull fastpow(ull a,ull b)
{
    ull ans=1;
    while(b)
    {
        if(b&1)
            ans*=a;
        b>>=1;
        a*=a;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);cin>>k;
    for(int i=n-1;i>=0;i--)
    {
        ull now=fastpow(2,i);
        if(k<now)
            printf("0");
        else    
            printf("1"),k=2*now-k-1;
    }
    return 0;
}