Submission #1362149

#TimeUsernameProblemLanguageResultExecution timeMemory
1362149iamhereforfunRack (eJOI19_rack)C++20
100 / 100
1 ms344 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int B = 18;
const long long K = 2;
const int LG = 20;
const int INF = 1e18 + 5;
const int P = 31;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {-1, 0, 1, 0};

long long n, k, ans, cur;

long long pw(long long a, long long b = MOD - 2)
{
    long long ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        a %= MOD;
        ans %= MOD;
        b >>= 1;
    }
    return ans;
}

inline void solve()
{
    cin >> n >> k;
    cur = pw(2, n - 1);
    while (k > 1)
    {
        if (k % 2 == 0) // right
        {
            ans += cur;
            ans %= MOD;
        }
        k = (k + 1) / 2;
        cur *= pw(2);
        cur %= MOD;
        // cout << cur << " " << ans << " " << k << "\n";
    }
    cout << ans + 1 << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...