Submission #853024

#	Time	Username	Problem	Language	Result	Execution time	Memory
853024		phathnv	Party (INOI20_party)	C++11	63 / 100	3034 ms	1252 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int pw[2][1 << 15];

void Add(int &x, const int &y) {
    x += y;
    if (x >= MOD)
        x -= MOD;
}

int Pow2(int k) {
    return 1ll * pw[0][k & ((1 << 15) - 1)] * pw[1][k >> 15] % MOD;
}

int Pow(int n, int k) {
    if (k == 0)
        return 1;
    int res = Pow(n, k >> 1);
    res = 1ll * res * res % MOD;
    if (k & 1)
        res = 1ll * res * n % MOD;
    return res;
}

void CalcCnt(long long n, vector<long long> &cnt) {
    int ptr = 0;
    for(long long x = 1; n > 0; x <<= 1) {
        cnt[ptr] = min(n, x);
        n -= cnt[ptr];
        ptr++;
    }
}

vector<long long> CalcNxtCnt(vector<long long> cnt, long long subtreeSize) {
    int sz = cnt.size();
    vector<long long> cntSubTree(cnt.size(), 0);
    CalcCnt(subtreeSize, cntSubTree);
    for(int i = 0; i < sz - 1; i++)
        cnt[i + 1] -= cntSubTree[i];
    for(int i = sz - 1; i >= 0; i--)
        cnt[i] = (i == 0 ? 0 : cnt[i - 1]);
    for(int i = 0; i < sz - 1; i++)
        cnt[i] += cntSubTree[i];
    return cnt;
}

int CalcContribute(vector<long long> cnt) {
    int val = 0, sz = cnt.size();
    vector<int> cntSubset(sz, 0);
    for(int i = sz - 2; i >= 0; i--)
        cnt[i] += cnt[i + 1];
    for(int i = 0; i < sz; i++) {
        cntSubset[i] = Pow2(cnt[i] % (MOD - 1));
        Add(cntSubset[i], MOD - 1);
    }
    for(int i = 0; i < sz - 1; i++)
        Add(val, 1ll * i * (cntSubset[i] - cntSubset[i + 1] + MOD) % MOD);
    return val;
}

int CalcComplete(long long n, vector<long long> cntRoot) {
    int k = 64 - __builtin_clzll(n);
    int sz = cntRoot.size();
    vector<vector<long long>> cnt(k, vector<long long>(sz, 0));
    cnt[0] = cntRoot;
    for(int i = 1; i < k; i++) {
        cnt[i] = cnt[i - 1];
        for(int j = i; j < k; j++)
            cnt[i][j - i + 1] -= (1ll << (j - i));
        for(int j = sz - 2; j >= 0; j--)
            cnt[i][j] = (j == 0? 0 : cnt[i][j - 1]);
        for(int j = i; j < k; j++)
            cnt[i][j - i] += (1ll << (j - i));
    }
    int sum = 0;
    for(int i = 0; i < k; i++)
        Add(sum, 1ll * CalcContribute(cnt[i]) * ((1ll << i) % MOD) % MOD);
    return sum;
}

int Calc(long long n, vector<long long> cntRoot) {
    if (n == 0)
        return 0;
    int k = 64 - __builtin_clzll(n);
    if (n == (1ll << k) - 1)
        return CalcComplete(n, cntRoot);
    long long lastLayer = n - ((1ll << (k - 1)) - 1);
    long long res = CalcContribute(cntRoot);
    long long numLeft, numRight;
    numLeft = numRight = (1ll << (k - 2)) - 1;
    numLeft += min(1ll << (k - 2), lastLayer);
    numRight += max(0ll, lastLayer - (1ll << (k - 2)));
    res += Calc(numLeft, CalcNxtCnt(cntRoot, numLeft));
    res += Calc(numRight, CalcNxtCnt(cntRoot, numRight));
    return res % MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    pw[0][0] = 1;
    for(int i = 1; i < (1 << 15); i++) {
        Add(pw[0][i], pw[0][i - 1]);
        Add(pw[0][i], pw[0][i - 1]);
    }
    for(int i = 0; i < (1 << 15); i++)
        pw[1][i] = Pow(pw[0][i], 1 << 15);
    int q;
    cin >> q;
    while (q--) {
        long long n;
        cin >> n;
        int k = 64 - __builtin_clzll(n);
        vector<long long> cntRoot(2 * k, 0);
        CalcCnt(n, cntRoot);
        cout << 1ll * Calc(n, cntRoot) * Pow(Pow2(n % (MOD - 1)) - 1 + MOD, MOD - 2) % MOD << '\n';
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 33 / 33
• Subtask 4: 0 / 37