Submission #1305879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305879		Newtonabc	Rack (eJOI19_rack)	C++20	40 / 100	1 ms	576 KiB

rack

#include<bits/stdc++.h>
#define ll long long
const ll MOD=1e9+7;
using namespace std;
ll mpow(int p){
    ll ret=1,mult=2;
    if(p>60) return LLONG_MAX;
    while(p){
        if(p&1) ret=(ret*mult)%MOD;
        p>>=1;
        mult=(mult*mult)%MOD;
    }
    return ret;
}
int cb(ll x){
    int ret=0;
    while(x) ret++,x>>=1;
    return ret;
}
int main(){
    ll n,k;
    cin>>n >>k;
    ll ret=0;
    if(cb(k)==n && (1<<n)==k){
        cout<<mpow(n);
        return 0;
    }
    k--;
    for(int i=0;i<n;i++){
        int po=n-i-1;
        //cout<<(1<<po) <<" ";
        bool fir;
        if(po>60 || k<(1LL<<po)) fir=1;
        else fir=0,k-=(1LL<<po);
        //cout<<fir <<" " ;
        if(fir==0) ret+=mpow(i);
        ret%=MOD;
    }
    cout<<ret+1LL;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 60