oj.uz

Submission #635472

# Submission time Handle Problem Language Result Execution time Memory
635472 2022-08-26T10:05:08 Z Cyanmond Party (INOI20_party) C++17
7 / 100
 3000 ms 3776 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);
}

std::array<i64, 100> p2m;

void init_p2() {
    p2m[0] = 2;
    for (int i = 0; i < 90; ++i) p2m[i + 1] = mul(p2m[i], p2m[i]);
}

std::unordered_map<i64, i64> p2memo;

i64 pow2(i64 n) {
    if (p2memo.find(n) != p2memo.end()) return p2memo[n];
    i64 n2 = n;
    i64 ret = 1;
    int i = 0;
    while (n != 0) {
        if (n & 1) mul_m(ret, p2m[i]);
        ++i;
        n >>= 1;
    }
    return p2memo[n2] = ret;
}

void solve() {
    // Time Complexity O(log^4 N)
    i64 N;
    std::cin >> N;
    // N = 2 ^ k - 1
    i64 k = 0;
    while ((1ll << k) - 1 < N) ++k;
    // assert((1ll << k) - 1 == N);

    std::vector<i64> red_vs = {N};
    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);
        }
    }

    // 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 <= 2 * 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];
                    }
                }
                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;
                    bool h = false;

                    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);
                        }
                    }
                    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 2 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 4 ms 316 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 36 ms 340 KB Output is correct
12 Correct 35 ms 336 KB Output is correct
13 Correct 33 ms 340 KB Output is correct
14 Correct 32 ms 332 KB Output is correct
15 Correct 33 ms 348 KB Output is correct
16 Correct 42 ms 336 KB Output is correct
17 Correct 34 ms 340 KB Output is correct
18 Correct 36 ms 328 KB Output is correct
19 Correct 37 ms 336 KB Output is correct
20 Correct 36 ms 212 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2390 ms 1068 KB Output is correct
2 Correct 2889 ms 1216 KB Output is correct
3 Correct 2525 ms 1272 KB Output is correct
4 Correct 2084 ms 1224 KB Output is correct
5 Correct 2676 ms 1344 KB Output is correct
6 Correct 2709 ms 1128 KB Output is correct
7 Correct 2345 ms 1288 KB Output is correct
8 Correct 2358 ms 1216 KB Output is correct
9 Correct 2266 ms 1144 KB Output is correct
10 Correct 2491 ms 1072 KB Output is correct
11 Execution timed out 3068 ms 400 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2105 ms 3492 KB Output is correct
2 Correct 2430 ms 3776 KB Output is correct
3 Correct 2032 ms 3384 KB Output is correct
4 Correct 2127 ms 3540 KB Output is correct
5 Correct 2603 ms 1480 KB Output is correct
6 Correct 2519 ms 1692 KB Output is correct
7 Correct 2475 ms 1640 KB Output is correct
8 Correct 2630 ms 1772 KB Output is correct
9 Correct 2345 ms 1396 KB Output is correct
10 Correct 2592 ms 1312 KB Output is correct
11 Execution timed out 3067 ms 360 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 4 ms 316 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 36 ms 340 KB Output is correct
12 Correct 35 ms 336 KB Output is correct
13 Correct 33 ms 340 KB Output is correct
14 Correct 32 ms 332 KB Output is correct
15 Correct 33 ms 348 KB Output is correct
16 Correct 42 ms 336 KB Output is correct
17 Correct 34 ms 340 KB Output is correct
18 Correct 36 ms 328 KB Output is correct
19 Correct 37 ms 336 KB Output is correct
20 Correct 36 ms 212 KB Output is correct
21 Correct 2390 ms 1068 KB Output is correct
22 Correct 2889 ms 1216 KB Output is correct
23 Correct 2525 ms 1272 KB Output is correct
24 Correct 2084 ms 1224 KB Output is correct
25 Correct 2676 ms 1344 KB Output is correct
26 Correct 2709 ms 1128 KB Output is correct
27 Correct 2345 ms 1288 KB Output is correct
28 Correct 2358 ms 1216 KB Output is correct
29 Correct 2266 ms 1144 KB Output is correct
30 Correct 2491 ms 1072 KB Output is correct
31 Execution timed out 3068 ms 400 KB Time limit exceeded
32 Halted 0 ms 0 KB -