Submission #1181905

#TimeUsernameProblemLanguageResultExecution timeMemory
1181905trufanov.pRack (eJOI19_rack)C++20
100 / 100
0 ms328 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

inline ll add(ll a, ll b, ll Mod) {
    return (a + b < Mod ? a + b : a + b - Mod);
}

inline ll mul(ll a, ll b, ll Mod) {
    return (a * b) % Mod;
}

ll binpow(ll a, ll b, ll Mod) {
    ll res = 1, cur = a;
    while (b) {
        if (b % 2 == 1) {
            res = mul(res, cur, Mod);
        }
        cur = mul(cur, cur, Mod);
        b /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    const ll Mod = 1e9 + 7;
    ll n, k;
    cin >> n >> k;
    k--;
    ll res = 0;
    ll cur = 0;
    for (ll b = n; b >= 1; --b) {
        if ((b - 1) <= 60 && k >= (1ll << (b - 1))) {
            ll p = binpow(2ll, cur, Mod);
            res = add(res, p, Mod);
            k -= (1ll << (b - 1));
        }
        cur++;
    }
    cout << res + 1 << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...