Submission #635467

# Submission time Handle Problem Language Result Execution time Memory
635467 2022-08-26T09:59:07 Z Cyanmond Party (INOI20_party) C++17
7 / 100
3000 ms 460 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]);
}

i64 pow2(i64 n) {
    i64 ret = 1;
    int i = 0;
    while (n != 0) {
        if (n & 1) mul_m(ret, p2m[i]);
        ++i;
        n >>= 1;
    }
    return 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();
}
# 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 3 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 3 ms 320 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 44 ms 336 KB Output is correct
12 Correct 36 ms 340 KB Output is correct
13 Correct 34 ms 336 KB Output is correct
14 Correct 34 ms 212 KB Output is correct
15 Correct 36 ms 344 KB Output is correct
16 Correct 33 ms 340 KB Output is correct
17 Correct 31 ms 212 KB Output is correct
18 Correct 32 ms 332 KB Output is correct
19 Correct 32 ms 340 KB Output is correct
20 Correct 33 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 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 3 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 3 ms 320 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 44 ms 336 KB Output is correct
12 Correct 36 ms 340 KB Output is correct
13 Correct 34 ms 336 KB Output is correct
14 Correct 34 ms 212 KB Output is correct
15 Correct 36 ms 344 KB Output is correct
16 Correct 33 ms 340 KB Output is correct
17 Correct 31 ms 212 KB Output is correct
18 Correct 32 ms 332 KB Output is correct
19 Correct 32 ms 340 KB Output is correct
20 Correct 33 ms 212 KB Output is correct
21 Execution timed out 3080 ms 460 KB Time limit exceeded
22 Halted 0 ms 0 KB -