Submission #1219724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219724		khome	Rack (eJOI19_rack)	C++20	In queue	0 ms	0 KiB

rack

#include <bits/stdc++.h>

using namespace std;

#define int long long
int mod = 1000000007;

int binpow(int n, int k) {
    if (k == 0) return 1;
    if (k % 2) return n * binpow(n, k - 1) % mod;
    int x = binpow(n, k / 2);
    return x * x % mod;
}

signed main() {
    int n, k;
    cin >> n >> k;

    vector <int> a; a.push_back(0);

    int N = binpow(2, n);
   
    int k2 = (k + 1) / 2 - 1; int x = 1;
    for (int j = 60; j >= 0; j --) {
        if ((k2 & (1ll << j)) == 0) continue;
        
        int y = binpow(2, j + 2);
        x += N * binpow(y, mod - 2) % mod;
        x %= mod;
    }

    if (k % 2 == 1) cout << x << endl;
    else cout << (x + N * binpow(2, mod - 2) % mod) % mod << endl;
    
    return 0;
}