oj.uz

Submission #633698

# Submission time Handle Problem Language Result Execution time Memory
633698 2022-08-23T05:33:14 Z 406 Party (INOI20_party) C++17
7 / 100
 3000 ms 979080 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 = 2.5e8;

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


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

ll p2(ll b) {
    ll a = pw(pw2[X], b / X);
    b %= X;
    a *= pw2[b];
    a %= MOD;
    return a;
}

void calc_dist(ll v, ll sub, int lg) {
    for (int k = lg; k < 62; k++) {
        int x = k - lg;
        if ((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; s != n; k++) {
        s += d[0][ptr][k] + d[1][ptr][k];
        q += p2(n - s) - 1;
        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; s != n; k++) {
        s += d[0][ptr][k] + d[1][ptr][k];
        ans += p2(n - s) - 1;
        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 1266 ms 978756 KB Output is correct
2 Correct 1267 ms 978696 KB Output is correct
3 Correct 1269 ms 979004 KB Output is correct
4 Correct 1265 ms 978752 KB Output is correct
5 Correct 1290 ms 978676 KB Output is correct
6 Correct 1271 ms 978960 KB Output is correct
7 Correct 1250 ms 978892 KB Output is correct
8 Correct 1240 ms 979068 KB Output is correct
9 Correct 1372 ms 978896 KB Output is correct
10 Correct 1255 ms 978784 KB Output is correct
11 Correct 1291 ms 979020 KB Output is correct
12 Correct 1300 ms 978948 KB Output is correct
13 Correct 1280 ms 978804 KB Output is correct
14 Correct 1263 ms 978800 KB Output is correct
15 Correct 1260 ms 978756 KB Output is correct
16 Correct 1254 ms 978804 KB Output is correct
17 Correct 1253 ms 978696 KB Output is correct
18 Correct 1280 ms 978752 KB Output is correct
19 Correct 1296 ms 978860 KB Output is correct
20 Correct 1244 ms 978952 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2040 ms 978984 KB Output is correct
2 Correct 2181 ms 978948 KB Output is correct
3 Correct 2089 ms 978928 KB Output is correct
4 Correct 1881 ms 979040 KB Output is correct
5 Correct 2106 ms 978852 KB Output is correct
6 Correct 2078 ms 978904 KB Output is correct
7 Correct 1987 ms 979008 KB Output is correct
8 Correct 2045 ms 979016 KB Output is correct
9 Correct 1955 ms 978920 KB Output is correct
10 Correct 2031 ms 978892 KB Output is correct
11 Execution timed out 3121 ms 978944 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1956 ms 978956 KB Output is correct
2 Correct 2084 ms 979080 KB Output is correct
3 Correct 1937 ms 978888 KB Output is correct
4 Correct 1998 ms 979040 KB Output is correct
5 Correct 2126 ms 979008 KB Output is correct
6 Correct 2057 ms 978900 KB Output is correct
7 Correct 2050 ms 978900 KB Output is correct
8 Correct 2109 ms 979048 KB Output is correct
9 Correct 2025 ms 978916 KB Output is correct
10 Correct 2117 ms 978960 KB Output is correct
11 Execution timed out 3111 ms 978896 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1266 ms 978756 KB Output is correct
2 Correct 1267 ms 978696 KB Output is correct
3 Correct 1269 ms 979004 KB Output is correct
4 Correct 1265 ms 978752 KB Output is correct
5 Correct 1290 ms 978676 KB Output is correct
6 Correct 1271 ms 978960 KB Output is correct
7 Correct 1250 ms 978892 KB Output is correct
8 Correct 1240 ms 979068 KB Output is correct
9 Correct 1372 ms 978896 KB Output is correct
10 Correct 1255 ms 978784 KB Output is correct
11 Correct 1291 ms 979020 KB Output is correct
12 Correct 1300 ms 978948 KB Output is correct
13 Correct 1280 ms 978804 KB Output is correct
14 Correct 1263 ms 978800 KB Output is correct
15 Correct 1260 ms 978756 KB Output is correct
16 Correct 1254 ms 978804 KB Output is correct
17 Correct 1253 ms 978696 KB Output is correct
18 Correct 1280 ms 978752 KB Output is correct
19 Correct 1296 ms 978860 KB Output is correct
20 Correct 1244 ms 978952 KB Output is correct
21 Correct 2040 ms 978984 KB Output is correct
22 Correct 2181 ms 978948 KB Output is correct
23 Correct 2089 ms 978928 KB Output is correct
24 Correct 1881 ms 979040 KB Output is correct
25 Correct 2106 ms 978852 KB Output is correct
26 Correct 2078 ms 978904 KB Output is correct
27 Correct 1987 ms 979008 KB Output is correct
28 Correct 2045 ms 979016 KB Output is correct
29 Correct 1955 ms 978920 KB Output is correct
30 Correct 2031 ms 978892 KB Output is correct
31 Execution timed out 3121 ms 978944 KB Time limit exceeded
32 Halted 0 ms 0 KB -