oj.uz

Submission #633687

# Submission time Handle Problem Language Result Execution time Memory
633687 2022-08-23T04:37:35 Z 406 Party (INOI20_party) C++17
7 / 100
 3000 ms 783332 KB 
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

#define forn(a, b) for (int a = 0; a < (b); a++)
#define rofn(a, b) for (int a = (b) - 1; a >= 0; a--)
#define LOG(a) (63 - __builtin_clzll(a))
#define chmx(a, b) a = max(a, b)
#define chmn(a, b) a = min(a, b)
#define pb push_back
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1,*p2;

/*inline int read() {
	ll x = 0, f = 1; char c;
	while(!isdigit(c = gc())) if(c=='-') f=-1;
	while(isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = gc();
	return x * f;
}
*/
const ll INFL = 1ll << 60;
const int INF = 1 << 29;
const int N = 62;
const int M = 2 * N;
const int MOD = 1e9 + 7;
const int X = 2e8;

ll d[2][M][M], ptr, q, ans, n;
int pw2[X];

ll pw(ll a, ll b) {
    b %= (MOD - 1);
    //a %= MOD;
    if (a == 2 && b < X) {
        return pw2[b];
    }
    ll re = 1;
    while (b) {
        if (b & 1)
            re = (re * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return re;
}

void calc_dist(ll v, ll sub, int lg) {
    for (int k = lg; k < 62; k++) {
        int x = k - lg;
        if ((x + lg) > 62 || (v << x) > n)
            d[1][ptr][x] = 0;
        else
            d[1][ptr][x] = min(n - (v << x) + 1, ((ll)1 << x));
    }
    if (v > 1) {
        for (int k = 2; k < N + 2; k++)
            d[0][ptr][k] -= d[1][ptr][k - 2];
    }
}

void pass() {
    for (int k = 1; k < M; k++)
        d[0][ptr + 1][k] = d[0][ptr][k - 1] + d[1][ptr][k - 1];
    ptr++;
}

void Complete(ll v, ll sub, int lg) {
    if (v > n) {
        ptr--;
        return;
    }
    //cout << "C: " << v << ' ' << sub << " PTR: " << ptr << '\n';
    calc_dist(v, sub, lg);

    pass();
    Complete(v << 1, sub >> 1, lg + 1);
    q <<= 1;
    if (q >= MOD)
        q -= MOD;

    ll s = 0;
    for (int k = 0; k < M; k++) {
        ll tmp = d[0][ptr][k] + d[1][ptr][k];
        s += tmp;
        ll t = pw(2, tmp) - 1;

        q += (k * t % MOD) * pw(2, n - s) % MOD;
        if (q >= MOD)
            q -= MOD;
    }
    ptr--;
}

void F(ll v, ll sub, int lg) {
    if (v > n) {
        ptr--;
        return;
    }
    //cout << "F: " << v << ' ' << sub << " PTR: " << ptr << '\n';
    calc_dist(v, sub, lg);

    ll r = (v << 1) | 1;
    ll l = (v << 1);
    int cntr = 0, cntl = 0;
    
    while (r <= n)
        r <<= 1, cntr++;
    while (l <= n)
        l <<= 1, cntl++;

    if (cntr == cntl) {
        q = 0;
        pass();
        Complete(v << 1, (1ll << cntl) - 1, lg + 1);
        ans += q;
        ans %= MOD;

        pass();
        F((v << 1) | 1, sub - (1ll << cntl), lg + 1);
    }
    else {
        q = 0;
        pass();
        Complete((v << 1) | 1, (1ll << cntr) - 1,lg + 1);

        ans += q;
        if (ans >= MOD)
            ans -= MOD;

        pass();
        F((v << 1), sub - (1ll << cntr), lg + 1);
    }
    

    ll s = 0;
    for (int k = 0; k < M; k++) {
        ll tmp = d[0][ptr][k] + d[1][ptr][k];
        s += tmp;
        ll t = pw(2, tmp) - 1;
        ans += k * t % MOD * pw(2, n - s) % MOD;
        if (ans >= MOD)
            ans -= MOD;
    }
    ptr--;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    pw2[0] = 1;
    for (int i = 1; i < X; i++) {
        pw2[i] = pw2[i - 1] * 2;
        if (pw2[i] >= MOD)
            pw2[i] -= MOD;
    }

    int query;
    cin >> query;
    while (query--) {
        cin >> n;

        F(1, n, 1);
        ll re = pw(2, n) - 1;

        ans = (ans * pw(re, MOD - 2)) % MOD;
        cout << ans << '\n';

        ans = q = ptr = 0;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 783048 KB Output is correct
2 Correct 1006 ms 783076 KB Output is correct
3 Correct 1018 ms 783060 KB Output is correct
4 Correct 1050 ms 783144 KB Output is correct
5 Correct 987 ms 783028 KB Output is correct
6 Correct 987 ms 783092 KB Output is correct
7 Correct 990 ms 783064 KB Output is correct
8 Correct 1004 ms 783144 KB Output is correct
9 Correct 1022 ms 783100 KB Output is correct
10 Correct 1024 ms 783100 KB Output is correct
11 Correct 1060 ms 783320 KB Output is correct
12 Correct 1069 ms 783028 KB Output is correct
13 Correct 1086 ms 783048 KB Output is correct
14 Correct 1088 ms 783092 KB Output is correct
15 Correct 1046 ms 783060 KB Output is correct
16 Correct 1078 ms 783140 KB Output is correct
17 Correct 1063 ms 783096 KB Output is correct
18 Correct 1079 ms 783120 KB Output is correct
19 Correct 1059 ms 783188 KB Output is correct
20 Correct 1063 ms 783276 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2404 ms 783332 KB Output is correct
2 Correct 2695 ms 783188 KB Output is correct
3 Correct 2455 ms 783212 KB Output is correct
4 Correct 2256 ms 783328 KB Output is correct
5 Correct 2510 ms 783200 KB Output is correct
6 Correct 2553 ms 783204 KB Output is correct
7 Correct 2360 ms 783200 KB Output is correct
8 Correct 2411 ms 783268 KB Output is correct
9 Correct 2337 ms 783180 KB Output is correct
10 Correct 2389 ms 783212 KB Output is correct
11 Execution timed out 3090 ms 783120 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2276 ms 783324 KB Output is correct
2 Correct 2493 ms 783208 KB Output is correct
3 Correct 2270 ms 783204 KB Output is correct
4 Correct 2305 ms 783204 KB Output is correct
5 Correct 2516 ms 783300 KB Output is correct
6 Correct 2450 ms 783280 KB Output is correct
7 Correct 2451 ms 783300 KB Output is correct
8 Correct 2528 ms 783128 KB Output is correct
9 Correct 2378 ms 783248 KB Output is correct
10 Correct 2523 ms 783292 KB Output is correct
11 Execution timed out 3122 ms 783136 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 783048 KB Output is correct
2 Correct 1006 ms 783076 KB Output is correct
3 Correct 1018 ms 783060 KB Output is correct
4 Correct 1050 ms 783144 KB Output is correct
5 Correct 987 ms 783028 KB Output is correct
6 Correct 987 ms 783092 KB Output is correct
7 Correct 990 ms 783064 KB Output is correct
8 Correct 1004 ms 783144 KB Output is correct
9 Correct 1022 ms 783100 KB Output is correct
10 Correct 1024 ms 783100 KB Output is correct
11 Correct 1060 ms 783320 KB Output is correct
12 Correct 1069 ms 783028 KB Output is correct
13 Correct 1086 ms 783048 KB Output is correct
14 Correct 1088 ms 783092 KB Output is correct
15 Correct 1046 ms 783060 KB Output is correct
16 Correct 1078 ms 783140 KB Output is correct
17 Correct 1063 ms 783096 KB Output is correct
18 Correct 1079 ms 783120 KB Output is correct
19 Correct 1059 ms 783188 KB Output is correct
20 Correct 1063 ms 783276 KB Output is correct
21 Correct 2404 ms 783332 KB Output is correct
22 Correct 2695 ms 783188 KB Output is correct
23 Correct 2455 ms 783212 KB Output is correct
24 Correct 2256 ms 783328 KB Output is correct
25 Correct 2510 ms 783200 KB Output is correct
26 Correct 2553 ms 783204 KB Output is correct
27 Correct 2360 ms 783200 KB Output is correct
28 Correct 2411 ms 783268 KB Output is correct
29 Correct 2337 ms 783180 KB Output is correct
30 Correct 2389 ms 783212 KB Output is correct
31 Execution timed out 3090 ms 783120 KB Time limit exceeded
32 Halted 0 ms 0 KB -