2セットのビットを使用して形成されたn番目の番号を見つけよう

Question

nが与えられていれば、ちょうど2ビットで形成できるn番目の番号を見つける必要があります。

良く明確にするために、シーケンスは、基本的には3,5,6,9,10のようになります。..

すなわち。

以下は、私が得た答えに基づいて行ったことです（それでも私には間違った答えが与えられます） ）いくつかの隠されたテストケースのため

using namespace std; 

#define MAX 10000 
#define MOD 1000000007 

long long int m[MAX+1]; 
long long int sum; 

long long int binary_search(long long int n) 
{ 
    long long int low=0,high=MAX,mid; 
    while(low<high) 
    { 
    mid=low+(high-low+1)/2; 
    if(m[mid]<=n) 
     low=mid; 
    else 
     high=mid-1; 
    } 
    return low; 
} 

int main() 
{ 
    m[0]=1; 
    for(long long int i=1;i<=MAX;i++) 
    m[i]=m[i-1]+i; 

    long long int n,k,l; 
    int t; 
    scanf("%d",&t); 
    for(int test=0;test<t;test++) 
    { 
    scanf("%lld",&n); 
    k=binary_search(n); 
    //cout<<m[k]<<" "; 
    l=n-m[k]; 
    cout<<((1<<k+1)%MOD+(1<<l)%MOD)%MOD<<"\n"; 
    } 
    return 0; 
} 

制約は1 < = T < = 10^6、1 < = N = 10^14 <あります。

Answer 1

パターンも見てみようMSB（最上位ビット）、インデックス= 1
とつの有効な数があり

MSB（最上位ビット）インデックス= 2
を持つ2つの有効数字は3つの有効な数字がありますがあります。 MSBと（最上位ビット）インデックス= 3（1001、1010、1100）
...

（インデックスkのMSBの後のkの場所がある）

だから、簡単にMSB FOのインデックスを見つけることができますnは所定のR - MSB = kが知られている場合だけ第二の非ゼロのビット（L）

Result = (1 << k) + (1 << l)