oj.uz

Submission #1003417

# Submission time Handle Problem Language Result Execution time Memory
1003417 2024-06-20T10:03:41 Z vjudge1 Party (INOI20_party) C++17
23 / 100
 39 ms 856 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9

const int MAX = 2e18 + 8, MOD = 1e9 + 7, LOGMAX = 200;
int n;
int Hcnt[LOGMAX][LOGMAX];
int RHcnt[LOGMAX][LOGMAX];

int binpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % MOD;
        b /= 2;
        a = a * a % MOD;
    }
    return res;
}
int inv(int a){
    return binpow(a, MOD - 2);
}

int ans[LOGMAX];

void solve(){
    int n; cin >> n;
    int LG = 0, T = 1;
    while(T <= n / 2) {LG++; T *= 2;}
    cout << ans[LG + 1] << '\n';
}

signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    for(int z = 1; z < 63; z++){
        n = (1ll << z) - 1;
        int res = 0;
        int LG = z - 1;
        for(int i = 0; (1ll << i) <= n; i++){
            for(int j = 0; j <= LG + i; j++){
                Hcnt[i][j] = 0;
                RHcnt[i][j] = 0;
            }
            for(int j = 0; j <= LG - i; j++){
                Hcnt[i][j] = (1ll << j);
                RHcnt[i][j] = (1ll << max(0ll, j - 1));
            }
            if(i != 0){
                for(int j = 0; j <= LG + i - 1; j++){
                    RHcnt[i][j + 1] += RHcnt[i - 1][j];
                    Hcnt[i][j + 1] += RHcnt[i - 1][j];
                }
            }
            int oth = n;
            for(int j = 0; j <= LG + i; j++){
                oth -= Hcnt[i][j];
                res = (res + j * (binpow(2, Hcnt[i][j]) - 1 + MOD) % MOD * binpow(2, oth + i) % MOD) % MOD;
            }
        }
        ans[z] = res * inv((binpow(2, n) - 1 + MOD) % MOD) % MOD;
    }
    int t; cin >> t;
    while(t--){
        solve();
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 588 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 36 ms 856 KB Output is correct
2 Correct 36 ms 600 KB Output is correct
3 Correct 33 ms 592 KB Output is correct
4 Correct 32 ms 604 KB Output is correct
5 Correct 32 ms 604 KB Output is correct
6 Correct 32 ms 604 KB Output is correct
7 Correct 33 ms 588 KB Output is correct
8 Correct 33 ms 604 KB Output is correct
9 Correct 33 ms 604 KB Output is correct
10 Correct 32 ms 604 KB Output is correct
11 Correct 39 ms 600 KB Output is correct
12 Correct 34 ms 600 KB Output is correct
13 Correct 37 ms 604 KB Output is correct
14 Correct 34 ms 600 KB Output is correct
15 Correct 37 ms 592 KB Output is correct
16 Correct 34 ms 596 KB Output is correct
17 Correct 35 ms 612 KB Output is correct
18 Correct 34 ms 604 KB Output is correct
19 Correct 34 ms 600 KB Output is correct
20 Correct 34 ms 604 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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