Submission #1221561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221561		mayac	Rack (eJOI19_rack)	C++20	40 / 100	886 ms	167936 KiB

rack

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll=unsigned long long;
const ll mod=(1e9)+7;

ll mypow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        return mypow((a*a)%mod,b/2)%mod;
    }
    return (a*(mypow((a*a)%mod,b/2)%mod))%mod;
}

ll calc(ll n,ll k){
    //cout<<n<<" "<<k<<"\n";
    if(k==1)return 1;
    ll p=0;
    while((ll(1)<<p)<k&&p<63)p++;
    p--;
    return (mypow(2,n-p-1)+calc(n,k-(1<<p)))%mod;

}

int main(){
    ll n,k,add;
    cin>>n>>k;
    cout<<calc(n,k)<<"\n";
}

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