oj.uz

Submission #635552

# Submission time Handle Problem Language Result Execution time Memory
635552 2022-08-26T12:41:04 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 35700 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;
        const auto v2 = v;
        v /= 2;
        --u;
        --d;
        int r = std::min(u, d);
        int l = std::max(0, (d + u - k + 2) / 2);
        i64 ret = 0;
        if (v != 0) {
            if (l <= r) {
                if (u == 0) ret = 1;
                else if (d >= u) {
                    const int t = u - l;
                    ret |= 1ll << t;
                } else {
                    const int t = u - d;
                    const int 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;
        }

        int 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;
        }


        i64 ln = 0, rn = 0;
        if (t == 0) {
            v >>= t;
            ln = v << (u - t);
            rn = ln + (1ll << (u - t));
        } else {
            --t;
            v >>= t;
            v ^= 1;
            t += 2;
            ln = v << (u - t);
            rn = ln + (1ll << (u - t));
        }
        ret -= std::max(0ll, std::min(rn - ln, rn - 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 35404 KB Output is correct
2 Correct 33 ms 35404 KB Output is correct
3 Correct 34 ms 35476 KB Output is correct
4 Correct 34 ms 35484 KB Output is correct
5 Correct 34 ms 35464 KB Output is correct
6 Correct 34 ms 35492 KB Output is correct
7 Correct 34 ms 35528 KB Output is correct
8 Correct 35 ms 35404 KB Output is correct
9 Correct 35 ms 35468 KB Output is correct
10 Correct 34 ms 35532 KB Output is correct
11 Correct 53 ms 35532 KB Output is correct
12 Correct 53 ms 35544 KB Output is correct
13 Correct 53 ms 35644 KB Output is correct
14 Correct 53 ms 35464 KB Output is correct
15 Correct 51 ms 35668 KB Output is correct
16 Correct 56 ms 35660 KB Output is correct
17 Correct 48 ms 35544 KB Output is correct
18 Correct 47 ms 35428 KB Output is correct
19 Correct 48 ms 35532 KB Output is correct
20 Correct 49 ms 35660 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 35568 KB Output is correct
2 Correct 287 ms 35568 KB Output is correct
3 Correct 269 ms 35560 KB Output is correct
4 Correct 252 ms 35564 KB Output is correct
5 Correct 297 ms 35548 KB Output is correct
6 Correct 280 ms 35576 KB Output is correct
7 Correct 245 ms 35528 KB Output is correct
8 Correct 260 ms 35660 KB Output is correct
9 Correct 249 ms 35700 KB Output is correct
10 Correct 299 ms 35564 KB Output is correct
11 Execution timed out 3073 ms 35656 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 35564 KB Output is correct
2 Correct 276 ms 35568 KB Output is correct
3 Correct 259 ms 35660 KB Output is correct
4 Correct 252 ms 35548 KB Output is correct
5 Correct 278 ms 35668 KB Output is correct
6 Correct 269 ms 35680 KB Output is correct
7 Correct 266 ms 35688 KB Output is correct
8 Correct 292 ms 35556 KB Output is correct
9 Correct 269 ms 35564 KB Output is correct
10 Correct 279 ms 35580 KB Output is correct
11 Correct 913 ms 35636 KB Output is correct
12 Correct 904 ms 35532 KB Output is correct
13 Correct 909 ms 35460 KB Output is correct
14 Correct 907 ms 35532 KB Output is correct
15 Correct 901 ms 35528 KB Output is correct
16 Correct 994 ms 35552 KB Output is correct
17 Correct 854 ms 35428 KB Output is correct
18 Correct 880 ms 35540 KB Output is correct
19 Correct 867 ms 35532 KB Output is correct
20 Correct 889 ms 35532 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35404 KB Output is correct
2 Correct 33 ms 35404 KB Output is correct
3 Correct 34 ms 35476 KB Output is correct
4 Correct 34 ms 35484 KB Output is correct
5 Correct 34 ms 35464 KB Output is correct
6 Correct 34 ms 35492 KB Output is correct
7 Correct 34 ms 35528 KB Output is correct
8 Correct 35 ms 35404 KB Output is correct
9 Correct 35 ms 35468 KB Output is correct
10 Correct 34 ms 35532 KB Output is correct
11 Correct 53 ms 35532 KB Output is correct
12 Correct 53 ms 35544 KB Output is correct
13 Correct 53 ms 35644 KB Output is correct
14 Correct 53 ms 35464 KB Output is correct
15 Correct 51 ms 35668 KB Output is correct
16 Correct 56 ms 35660 KB Output is correct
17 Correct 48 ms 35544 KB Output is correct
18 Correct 47 ms 35428 KB Output is correct
19 Correct 48 ms 35532 KB Output is correct
20 Correct 49 ms 35660 KB Output is correct
21 Correct 294 ms 35568 KB Output is correct
22 Correct 287 ms 35568 KB Output is correct
23 Correct 269 ms 35560 KB Output is correct
24 Correct 252 ms 35564 KB Output is correct
25 Correct 297 ms 35548 KB Output is correct
26 Correct 280 ms 35576 KB Output is correct
27 Correct 245 ms 35528 KB Output is correct
28 Correct 260 ms 35660 KB Output is correct
29 Correct 249 ms 35700 KB Output is correct
30 Correct 299 ms 35564 KB Output is correct
31 Execution timed out 3073 ms 35656 KB Time limit exceeded
32 Halted 0 ms 0 KB -