Submission #635561

# Submission time Handle Problem Language Result Execution time Memory
635561 2022-08-26T12:58:01 Z Cyanmond Party (INOI20_party) C++17
0 / 100
328 ms 35568 KB
#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 mod = 1000000007;

i64 nmr(i64 a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}

i64 add(i64 a, i64 b) {
    a += b;
    if (a > mod) a -= mod;
    return a;
}
i64 mul(i64 a, i64 b) { return a * b % mod; }
void add_m(i64 &a, i64 b) { a = add(a, b); }
void mul_m(i64 &a, i64 b) { a = mul(a, b); }

i64 inv(i64 x) {
    i64 a = x, b = mod, u = 1, v = 0, t = 0;
    while (b > 0) {
        t = a / b;
        a -= t * b;
        u -= t * v;
        std::swap(a, b);
        std::swap(u, v);
    }
    return nmr(u);
}

constexpr i64 width = 1500000;
std::array<i64, width> pa, pb, pc;

void init_p2() {
    pa[0] = 1;
    for (int i = 1; i < width; ++i) pa[i] = mul(pa[i - 1], 2);
    pb[0] = 1;
    const i64 v1 = mul(pa.back(), 2);
    for (int i = 1; i < width; ++i) pb[i] = mul(pb[i - 1], v1);
    pc[0] = 1;
    const i64 v2 = mul(pb.back(), v1);
    for (int i = 1; i < width; ++i) pc[i] = mul(pc[i - 1], v2);
}

std::unordered_map<i64, i64> p2memo;

i64 pow2(i64 n) {
    const i64 v1 = n / (width * width);
    i64 ret = pc[v1];
    n -= width * width * v1;
    const i64 v2 = n / width;
    mul_m(ret, pb[v2]);
    n -= width * v2;
    return mul(ret, pa[n]);
}

void solve() {
    // Time Complexity O(log^4 N)
    i64 N;
    std::cin >> N;
    // N = 2 ^ k - 1
    int k = 0;
    while ((1ll << k) - 1 < N) ++k;
    // assert((1ll << k) - 1 == N);
 
    std::vector<i64> red_vs = {N + 1};
    while (red_vs.back() != 1) {
        red_vs.push_back(red_vs.back() / 2);
    }
    std::reverse(red_vs.begin(), red_vs.end());
 
    std::vector<std::vector<i64>> red_count_vs(k);
    for (int i = k - 1; i >= 0; --i) {
        red_count_vs[i].assign(k - i, 0);
        red_count_vs[i][0] = 1;
        for (int j = 1; j < k - i; ++j) red_count_vs[i][j] += red_count_vs[i + 1][j - 1];
        if (i != k - 1 and red_vs[i + 1] == 2 * red_vs[i] + 1) {
            for (int j = 1; j < k - i; ++j) red_count_vs[i][j] += 1ll << (j - 1);
        } else {
            for (int j = 1; j < k - i - 1; ++j) red_count_vs[i][j] += 1ll << (j - 1);
        }
    }

    auto count_vs = [&](i64 v, int d, int u) -> i64 {
        if (u == 0) return 1;
        static int l, r, t, q;
        static i64 v2, ret;
        v2 = v;
        v /= 2;
        --u;
        --d;
        r = std::min(u, d);
        l = std::max(0, (d + u - k) / 2 + 1);
        ret = 0;
        if (v != 0) {
            if (l <= r) {
                if (u == 0) ret = 1;
                else if (d >= u) {
                    t = u - l;
                    ret |= 1ll << t;
                } else {
                    t = u - d;
                    q = t + (r - l);
                    ret |= (1ll << q) - 1;
                    ret -= (1ll << (t - 1)) - 1;
                }
            }
        }
        v = v2;
        ++u;
        ++d;
        ++l;
        ++r;
        if (d + u < k) {
            --l;
            ret += 1ll << u;
        }

        t = (d + u - k + 1) / 2;
        if (t < 0) return ret;
        if (d + u - 2 * t != k - 1) {
            return ret;
        }
        if (not(l <= t and t <= r)) {
            return ret;
        }

        static i64 ln, wn;
        ln = 0, wn = 0;
        if (t == 0) {
            v >>= t;
            ln = v << (u - t);
            wn = 1ll << (u - t);
        } else {
            v >>= --t;
            v ^= 1;
            t += 2;
            ln = v << (u - t);
            wn = 1ll << (u - t);
        }
        ret -= std::max(0ll, std::min(wn, ln + wn - N - 1));
        return ret;
    };

    // sa0te
    auto dfs = [&](auto &&self, const int d, const i64 v) -> i64 {
        if (v > N) return 0;
        i64 ret = 0;
        if (red_vs[d] == v) {
            // rec
            add_m(ret, self(self, d + 1, 2 * v));
            add_m(ret, self(self, d + 1, 2 * v + 1));
 
            i64 sum = 0;
            for (int u = 0; u <= d + k; ++u) {
                i64 count_v = count_vs(v, d, u);
                if (count_v == 0) continue;
                add_m(ret, mul(u, add(pow2(N - sum), mod - pow2(N - sum - count_v))));
                sum += count_v;
            }
        } else {
            // no rec
            for (int fd = d; fd < k; ++fd) {
                if (v * (1ll << (fd - d)) > N) continue;
                const i64 ms = nmr(1ll << (fd - d));
                i64 sum = 0;
                for (int u = 0; u <= fd + k; ++u) {
                    i64 count_v = count_vs(v << (fd - d), fd, u);
                    if (count_v == 0) continue;
                    add_m(ret, mul(mul(ms, u), add(pow2(N - sum), mod - pow2(N - sum - count_v))));
                    sum += count_v;
                }
            }
        }
 
        return ret;
    };
    const auto res = dfs(dfs, 0, 1);
 
    std::cout << nmr(res * inv(add(pow2(N), mod - 1))) << std::endl;
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    init_p2();
    int Q;
    std::cin >> Q;
    while (Q--) solve();
}
# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 35500 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 35564 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 312 ms 35568 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 35500 KB Output isn't correct
2 Halted 0 ms 0 KB -