oj.uz

Submission #635877

# Submission time Handle Problem Language Result Execution time Memory
635877 2022-08-27T09:05:29 Z K4YAN Party (INOI20_party) C++17
0 / 100
 75 ms 428 KB 
//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 ans[mxn], idk[mxn], dis[2 * 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;
        dis[d] %= md;
        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 % md, 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] > -1) {
        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 << ans[mxh] << "\n";
    return;

}

int main() {

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

    fill(ans, ans + mxn, -1);
    fun();
    cin >> t;
    while(t--) {
        input(), solve();
    }

    return 0;
    
}
/*
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -