Submission #633680

#	Time	Username	Problem	Language	Result	Execution time	Memory
633680		406	Party (INOI20_party)	C++17	7 / 100	3091 ms	540 KiB

Main

#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() {
	int 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 = 122;
const int MOD = 1e9 + 7;

ll d[2][N][N], ptr, q, ans, n;

ll pw(ll a, ll b) {
    assert(b >= 0);
    b %= (MOD - 1);
    a %= MOD;

    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)
            break;
        d[1][ptr][x] = min(n - (v << x) + 1, ((ll)1 << x));
    }
    if (v > 1) {
        for (int k = 2; k < N; k++)
            d[0][ptr][k] -= d[1][ptr][k - 2];
    }
}

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

void clear() {
    for (int b = 0; b < 2; b++)
        for (int i = 0; i < N; i++)
            d[b][ptr][i] = 0;
    ptr--;
}

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

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

    ll s = 0;
    for (int k = 0; k < N; k++) {
        if (!d[0][ptr][k] && !d[1][ptr][k])
            continue;
        s += d[0][ptr][k] + d[1][ptr][k];
        ll t = pw(2, d[0][ptr][k] + d[1][ptr][k]) - 1;

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

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

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

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

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

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

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

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

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37