oj.uz

Submission #635885

# Submission time Handle Problem Language Result Execution time Memory
635885 2022-08-27T09:17:31 Z K4YAN Party (INOI20_party) C++17
23 / 100
 83 ms 488 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 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.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
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 440 KB Output is correct
2 Correct 81 ms 424 KB Output is correct
3 Correct 83 ms 436 KB Output is correct
4 Correct 83 ms 420 KB Output is correct
5 Correct 83 ms 424 KB Output is correct
6 Correct 82 ms 420 KB Output is correct
7 Correct 77 ms 428 KB Output is correct
8 Correct 82 ms 428 KB Output is correct
9 Correct 82 ms 424 KB Output is correct
10 Correct 76 ms 436 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 488 KB Output is correct
13 Correct 7 ms 468 KB Output is correct
14 Correct 6 ms 464 KB Output is correct
15 Correct 6 ms 488 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 6 ms 488 KB Output is correct
18 Correct 7 ms 468 KB Output is correct
19 Correct 7 ms 468 KB Output is correct
20 Correct 8 ms 480 KB Output is correct

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 -