oj.uz

Submission #635567

# Submission time Handle Problem Language Result Execution time Memory
635567 2022-08-26T13:02:50 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 35680 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 ret, ln, wn;
        const auto v2 = v;
        v /= 2;
        --u;
        --d;
        r = std::min(u, d);
        l = std::max(0, (d + u - k + 2) / 2);
        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;
        }

        ln = 0, wn = 0;
        if (t == 0) {
            v >>= t;
            ln = v << (u - t);
            wn = 1ll << (u - t);
        } else {
            --t;
            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 = 0;
                /*
                for (i64 p = 0; p <= u; ++p) {
                    const i64 now_d = d - p;
                    if (now_d < 0) continue;
                    const i64 t = u - p;
                    if (now_d + t >= k) continue;
                    
                    if (t == 0) ++count_v;
                    else {
                        if (p == 0) count_v += red_count_vs[now_d][t];
                        else count_v += red_count_vs[now_d][t] - red_count_vs[now_d + 1][t - 1];
                    }
                }*/
                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
            i64 v2 = v;
            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 = 0;

/*
                    for (int p = 0; p <= std::min(u, fd); ++p) {
                        const int now_d = fd - p;
                        bool th = false;
                        if (red_vs[now_d] == v2 / (1ll << p)) th = true;
                        const int t = u - p;
                        if (now_d + t >= k) {
                            if (th) h = true;
                            continue;
                        }
 
                        if (th) {
                            if (t == 0) ++count_v;
                            else {
                                if (h) count_v += red_count_vs[now_d][t] - red_count_vs[now_d + 1][t - 1];
                                else count_v += red_count_vs[now_d + 1][t - 1];
                            }
                            h = true;
                        } else {
                            if (v % 2 == 1 and now_d + t == k - 1) continue;
                            count_v += 1ll << (p != 0 and t != 0 ? t - 1 : t);
                        }
                    }*/
                    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;
                }
                v2 *= 2;
            }
        }
 
        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();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35420 KB Output is correct
2 Correct 35 ms 35476 KB Output is correct
3 Correct 33 ms 35468 KB Output is correct
4 Correct 36 ms 35436 KB Output is correct
5 Correct 36 ms 35484 KB Output is correct
6 Correct 39 ms 35456 KB Output is correct
7 Correct 35 ms 35404 KB Output is correct
8 Correct 34 ms 35428 KB Output is correct
9 Correct 33 ms 35404 KB Output is correct
10 Correct 33 ms 35428 KB Output is correct
11 Correct 53 ms 35484 KB Output is correct
12 Correct 52 ms 35532 KB Output is correct
13 Correct 51 ms 35532 KB Output is correct
14 Correct 54 ms 35500 KB Output is correct
15 Correct 54 ms 35556 KB Output is correct
16 Correct 51 ms 35452 KB Output is correct
17 Correct 50 ms 35532 KB Output is correct
18 Correct 49 ms 35528 KB Output is correct
19 Correct 48 ms 35468 KB Output is correct
20 Correct 51 ms 35504 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 35568 KB Output is correct
2 Correct 318 ms 35568 KB Output is correct
3 Correct 347 ms 35612 KB Output is correct
4 Correct 245 ms 35640 KB Output is correct
5 Correct 290 ms 35680 KB Output is correct
6 Correct 303 ms 35548 KB Output is correct
7 Correct 259 ms 35548 KB Output is correct
8 Correct 320 ms 35572 KB Output is correct
9 Correct 264 ms 35568 KB Output is correct
10 Correct 324 ms 35568 KB Output is correct
11 Execution timed out 3075 ms 35548 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 35556 KB Output is correct
2 Correct 289 ms 35480 KB Output is correct
3 Correct 248 ms 35556 KB Output is correct
4 Correct 261 ms 35560 KB Output is correct
5 Correct 285 ms 35604 KB Output is correct
6 Correct 306 ms 35568 KB Output is correct
7 Correct 284 ms 35572 KB Output is correct
8 Correct 293 ms 35568 KB Output is correct
9 Correct 291 ms 35660 KB Output is correct
10 Correct 290 ms 35516 KB Output is correct
11 Correct 939 ms 35468 KB Output is correct
12 Correct 947 ms 35540 KB Output is correct
13 Correct 1008 ms 35544 KB Output is correct
14 Correct 999 ms 35460 KB Output is correct
15 Correct 1014 ms 35484 KB Output is correct
16 Correct 970 ms 35540 KB Output is correct
17 Correct 957 ms 35532 KB Output is correct
18 Correct 914 ms 35540 KB Output is correct
19 Correct 967 ms 35616 KB Output is correct
20 Correct 1111 ms 35436 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35420 KB Output is correct
2 Correct 35 ms 35476 KB Output is correct
3 Correct 33 ms 35468 KB Output is correct
4 Correct 36 ms 35436 KB Output is correct
5 Correct 36 ms 35484 KB Output is correct
6 Correct 39 ms 35456 KB Output is correct
7 Correct 35 ms 35404 KB Output is correct
8 Correct 34 ms 35428 KB Output is correct
9 Correct 33 ms 35404 KB Output is correct
10 Correct 33 ms 35428 KB Output is correct
11 Correct 53 ms 35484 KB Output is correct
12 Correct 52 ms 35532 KB Output is correct
13 Correct 51 ms 35532 KB Output is correct
14 Correct 54 ms 35500 KB Output is correct
15 Correct 54 ms 35556 KB Output is correct
16 Correct 51 ms 35452 KB Output is correct
17 Correct 50 ms 35532 KB Output is correct
18 Correct 49 ms 35528 KB Output is correct
19 Correct 48 ms 35468 KB Output is correct
20 Correct 51 ms 35504 KB Output is correct
21 Correct 292 ms 35568 KB Output is correct
22 Correct 318 ms 35568 KB Output is correct
23 Correct 347 ms 35612 KB Output is correct
24 Correct 245 ms 35640 KB Output is correct
25 Correct 290 ms 35680 KB Output is correct
26 Correct 303 ms 35548 KB Output is correct
27 Correct 259 ms 35548 KB Output is correct
28 Correct 320 ms 35572 KB Output is correct
29 Correct 264 ms 35568 KB Output is correct
30 Correct 324 ms 35568 KB Output is correct
31 Execution timed out 3075 ms 35548 KB Time limit exceeded
32 Halted 0 ms 0 KB -