Submission #635885

#	Time	Username	Problem	Language	Result	Execution time	Memory
635885		K4YAN	Party (INOI20_party)	C++17	23 / 100	83 ms	488 KiB

Main

//Be Name Khoda

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define pllll pair<pll, pll>
#define all(x) x.begin(), x.end()

const ll mxn = 62, md = 1e9 + 7;
ll n, t, mxh, q, w, ans2;
ll idk[mxn], dis[2 * mxn], ans[mxn];

inline void fun() {
    idk[0] = 1;
    for(int i = 1; i < mxn; i++) {
        idk[i] = 2LL * idk[i - 1] + 1;
    } return;
}

ll tav(ll a, ll b) {
    ll res = 1;
    while(b > 0) {
        if(b & 1) res = res * a % md;
        a = a * a % md, b >>= 1;
    } return res;
}

inline void input() {

    cin >> n;
    for(int i = 0; i < mxn; i++) {
        if(idk[i] == n) {
            mxh = i;
            break;
        }
    }

}

void BFS(int h) {
    fill(dis, dis + 2 * mxn, 0);
    int ptr = 0;
    vector<pllll> bfs;
    bfs.push_back({{1, 0}, {-1, h}});
    while(ptr < int(bfs.size())) {
        auto x = bfs[ptr++];
        ll tp = x.second.first, num = x.first.first, d = x.first.second;
        h = x.second.second;
        dis[d] += num;
        if(tp == -1) {
            if(h > 0) {
                bfs.push_back({{1, 1}, {1, h - 1}});
            }
            if(h < mxh) {
                bfs.push_back({{2, 1}, {0, h + 1}});
            } continue;
        } 
        if(tp == 0) {
            if(h < mxh) {
                bfs.push_back({{num * 2, d + 1}, {0, h + 1}});
            } continue;
        }
        if(tp == 1) {
            if(h > 0) {
                bfs.push_back({{1, d + 1}, {1, h - 1}});
            } bfs.push_back({{num, d + 1}, {0, h + 1}});
        } continue;
    }
    return;
}

inline void solve() {

    if(ans[mxh]) {
        cout << ans[mxh] << "\n";
        return;
    }
    ans2 = 0;
    for(int i = 0; i <= mxh; i++) {
        BFS(i);
        ll sum = 0, pw = 0;
        for(int j = 0; j < 2 * mxn; j++) {
            if(dis[j] == 0) break;
            q = tav(tav(2, n) - 1, md - 2);
            w = tav(2, dis[j]) - 1;
            w = w * 1 * tav(2, n - sum - dis[j]) % md;
            pw = (pw + (q * w % md * j % md)) % md;
            sum += dis[j];
        }
        pw = pw * tav(2, i) % md;
        ans2 += pw;
    } ans2 %= md;
    ans[mxh] = ans2;
    cout << ans2 << "\n";
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    fun();
    cin >> t;
    while(t--) {
        input(), solve();
    }

    return 0;
    
}
/*
*/

• Subtask 1: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37