oj.uz

Submission #635496

# Submission time Handle Problem Language Result Execution time Memory
635496 2022-08-26T10:37:51 Z Cyanmond Party (INOI20_party) C++17
7 / 100
 1919 ms 26288 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 = 1100000;
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;
    ret *= pb[v2];
    n -= width * v2;
    return ret * pa[n];
}

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 26 ms 26056 KB Output is correct
2 Correct 25 ms 26028 KB Output is correct
3 Correct 25 ms 26060 KB Output is correct
4 Correct 26 ms 26056 KB Output is correct
5 Correct 28 ms 26176 KB Output is correct
6 Correct 28 ms 26104 KB Output is correct
7 Correct 25 ms 26060 KB Output is correct
8 Correct 27 ms 26148 KB Output is correct
9 Correct 25 ms 26136 KB Output is correct
10 Correct 26 ms 26080 KB Output is correct
11 Correct 45 ms 26056 KB Output is correct
12 Correct 44 ms 26160 KB Output is correct
13 Correct 43 ms 26072 KB Output is correct
14 Correct 46 ms 26060 KB Output is correct
15 Correct 50 ms 26036 KB Output is correct
16 Correct 46 ms 26200 KB Output is correct
17 Correct 44 ms 26068 KB Output is correct
18 Correct 45 ms 26284 KB Output is correct
19 Correct 45 ms 26164 KB Output is correct
20 Correct 45 ms 26152 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1919 ms 26288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1793 ms 26288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 26056 KB Output is correct
2 Correct 25 ms 26028 KB Output is correct
3 Correct 25 ms 26060 KB Output is correct
4 Correct 26 ms 26056 KB Output is correct
5 Correct 28 ms 26176 KB Output is correct
6 Correct 28 ms 26104 KB Output is correct
7 Correct 25 ms 26060 KB Output is correct
8 Correct 27 ms 26148 KB Output is correct
9 Correct 25 ms 26136 KB Output is correct
10 Correct 26 ms 26080 KB Output is correct
11 Correct 45 ms 26056 KB Output is correct
12 Correct 44 ms 26160 KB Output is correct
13 Correct 43 ms 26072 KB Output is correct
14 Correct 46 ms 26060 KB Output is correct
15 Correct 50 ms 26036 KB Output is correct
16 Correct 46 ms 26200 KB Output is correct
17 Correct 44 ms 26068 KB Output is correct
18 Correct 45 ms 26284 KB Output is correct
19 Correct 45 ms 26164 KB Output is correct
20 Correct 45 ms 26152 KB Output is correct
21 Incorrect 1919 ms 26288 KB Output isn't correct
22 Halted 0 ms 0 KB -