oj.uz

Submission #635633

# Submission time Handle Problem Language Result Execution time Memory
635633 2022-08-26T14:11:56 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 65100 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 = 1 << 17;
std::array<i64, width> pa, pb;

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

inline i64 pow2(i64 n) {
    static int v1, v2;
    n %= mod - 1;
    v2 = n / width;
    i64 ret = pb[v2];
    n -= width * v2;
    return mul(ret, pa[n]);
}

std::array<std::array<std::array<i64, 200>, 200>, 200> cv_m;

void solve() {
    // Time Complexity O(log^3 N)
    i64 N;
    std::cin >> N;
    // N = 2 ^ k - 1
    int k = 0;
    while ((1ll << k) - 1 < N) ++k;
 
    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());

    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;

        if (cv_m[k][d][u] != -1) {
            ret = cv_m[k][d][u];
            r = std::min(u, d);
            l = std::max(0, (d + u - k + 2) / 2);
            if (d + u < k) --l;
        } else {
            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 (d != -1) {
                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;
            }
            cv_m[k][d][u] = ret;
        }

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

    i64 pow2_N = pow2(N);
    // 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, memo = pow2_N;
            for (int u = 0; u <= d + k; ++u) {
                const i64 count_v = count_vs(v, d, u);
                if (count_v == 0) continue;
                i64 new_memo = pow2(N - sum - count_v);
                add_m(ret, mul(u, add(memo, mod - new_memo)));
                sum += count_v;
                memo = new_memo;
            }
        } else {
            // no rec
            for (int fd = d; fd < k; ++fd) {
                if (v * (1ll << (fd - d)) > N) continue;
                const i64 ms = nmr(1ll << (fd - d));
                i64 msm = -ms;
                i64 sum = 0, memo = pow2_N;
                for (int u = 0; u <= fd + k; ++u) {
                    add_m(msm, ms);
                    const i64 count_v = count_vs(v << (fd - d), fd, u);
                    if (count_v == 0) continue;
                    i64 new_memo = pow2(N - sum - count_v);
                    add_m(ret, mul(msm, add(memo, mod - new_memo)));
                    sum += count_v;
                    memo = new_memo;
                }
            }
        }
 
        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();
    for (auto &a : cv_m) for (auto &b : a) for (auto &c : b) c = -1;
    int Q;
    std::cin >> Q;
    while (Q--) solve();
}

Compilation message

Main.cpp: In function 'i64 pow2(i64)':
Main.cpp:46:16: warning: unused variable 'v1' [-Wunused-variable]
   46 |     static int v1, v2;
      |                ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 64856 KB Output is correct
2 Correct 31 ms 64976 KB Output is correct
3 Correct 30 ms 64880 KB Output is correct
4 Correct 29 ms 64992 KB Output is correct
5 Correct 29 ms 64900 KB Output is correct
6 Correct 29 ms 64860 KB Output is correct
7 Correct 28 ms 64980 KB Output is correct
8 Correct 29 ms 64932 KB Output is correct
9 Correct 34 ms 64984 KB Output is correct
10 Correct 29 ms 64900 KB Output is correct
11 Correct 43 ms 64972 KB Output is correct
12 Correct 47 ms 64996 KB Output is correct
13 Correct 51 ms 65000 KB Output is correct
14 Correct 45 ms 65036 KB Output is correct
15 Correct 43 ms 65004 KB Output is correct
16 Correct 42 ms 64936 KB Output is correct
17 Correct 39 ms 64972 KB Output is correct
18 Correct 40 ms 64912 KB Output is correct
19 Correct 40 ms 64992 KB Output is correct
20 Correct 42 ms 64912 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 64916 KB Output is correct
2 Correct 227 ms 64984 KB Output is correct
3 Correct 207 ms 64980 KB Output is correct
4 Correct 194 ms 64892 KB Output is correct
5 Correct 213 ms 64980 KB Output is correct
6 Correct 212 ms 64980 KB Output is correct
7 Correct 206 ms 65100 KB Output is correct
8 Correct 196 ms 64980 KB Output is correct
9 Correct 194 ms 64972 KB Output is correct
10 Correct 220 ms 64896 KB Output is correct
11 Execution timed out 3030 ms 65028 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 64980 KB Output is correct
2 Correct 213 ms 64876 KB Output is correct
3 Correct 187 ms 64972 KB Output is correct
4 Correct 203 ms 64940 KB Output is correct
5 Correct 217 ms 64980 KB Output is correct
6 Correct 206 ms 64900 KB Output is correct
7 Correct 244 ms 64992 KB Output is correct
8 Correct 211 ms 64972 KB Output is correct
9 Correct 200 ms 64972 KB Output is correct
10 Correct 287 ms 65080 KB Output is correct
11 Correct 726 ms 64912 KB Output is correct
12 Correct 693 ms 64960 KB Output is correct
13 Correct 725 ms 64972 KB Output is correct
14 Correct 702 ms 64980 KB Output is correct
15 Correct 714 ms 64956 KB Output is correct
16 Correct 731 ms 64980 KB Output is correct
17 Correct 691 ms 64980 KB Output is correct
18 Correct 687 ms 64980 KB Output is correct
19 Correct 739 ms 64888 KB Output is correct
20 Correct 735 ms 64980 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 64856 KB Output is correct
2 Correct 31 ms 64976 KB Output is correct
3 Correct 30 ms 64880 KB Output is correct
4 Correct 29 ms 64992 KB Output is correct
5 Correct 29 ms 64900 KB Output is correct
6 Correct 29 ms 64860 KB Output is correct
7 Correct 28 ms 64980 KB Output is correct
8 Correct 29 ms 64932 KB Output is correct
9 Correct 34 ms 64984 KB Output is correct
10 Correct 29 ms 64900 KB Output is correct
11 Correct 43 ms 64972 KB Output is correct
12 Correct 47 ms 64996 KB Output is correct
13 Correct 51 ms 65000 KB Output is correct
14 Correct 45 ms 65036 KB Output is correct
15 Correct 43 ms 65004 KB Output is correct
16 Correct 42 ms 64936 KB Output is correct
17 Correct 39 ms 64972 KB Output is correct
18 Correct 40 ms 64912 KB Output is correct
19 Correct 40 ms 64992 KB Output is correct
20 Correct 42 ms 64912 KB Output is correct
21 Correct 238 ms 64916 KB Output is correct
22 Correct 227 ms 64984 KB Output is correct
23 Correct 207 ms 64980 KB Output is correct
24 Correct 194 ms 64892 KB Output is correct
25 Correct 213 ms 64980 KB Output is correct
26 Correct 212 ms 64980 KB Output is correct
27 Correct 206 ms 65100 KB Output is correct
28 Correct 196 ms 64980 KB Output is correct
29 Correct 194 ms 64972 KB Output is correct
30 Correct 220 ms 64896 KB Output is correct
31 Execution timed out 3030 ms 65028 KB Time limit exceeded
32 Halted 0 ms 0 KB -