oj.uz

Submission #635646

# Submission time Handle Problem Language Result Execution time Memory
635646 2022-08-26T15:04:22 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 65040 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(int n) {
    static int v1, v2;
    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;

constexpr i64 danger_limit = 8000000000000000000ll;

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;
            }
            ret %= mod - 1;
            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)) % (mod - 1);
        if (ret < 0) ret += mod - 1;
        return ret;
    };

    i64 pow2_N = pow2(N % (mod - 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, memo = pow2_N;
            int n = N % (mod - 1);
            for (int u = 0; u <= d + k; ++u) {
                const i64 count_v = count_vs(v, d, u);
                if (count_v == 0) continue;
                int new_n = n - count_v;
                if (new_n < 0) new_n += mod - 1;
                i64 new_memo = pow2(new_n);
                add_m(ret, u * add(memo, mod - new_memo));
                sum += count_v;
                memo = new_memo;
                n = new_n;
            }
            ret %= mod;
        } 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;
                int n = N % (mod - 1);
                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;
                    int new_n = n - count_v;
                    if (new_n < 0) new_n += mod - 1;
                    i64 new_memo = pow2(new_n);
                    add_m(ret, msm * add(memo, mod - new_memo));
                    if (ret > danger_limit) ret %= mod;
                    sum += count_v;
                    memo = new_memo;
                    n = new_n;
                }
            }
        }
 
        return ret;
    };
    const auto res = dfs(dfs, 0, 1);
 
    std::cout << nmr(res * inv(add(pow2(N % (mod - 1)), 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(int)':
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 30 ms 64980 KB Output is correct
2 Correct 30 ms 64972 KB Output is correct
3 Correct 31 ms 64884 KB Output is correct
4 Correct 34 ms 64972 KB Output is correct
5 Correct 32 ms 64992 KB Output is correct
6 Correct 28 ms 64968 KB Output is correct
7 Correct 30 ms 64976 KB Output is correct
8 Correct 29 ms 64908 KB Output is correct
9 Correct 33 ms 64980 KB Output is correct
10 Correct 30 ms 64980 KB Output is correct
11 Correct 42 ms 64948 KB Output is correct
12 Correct 43 ms 64956 KB Output is correct
13 Correct 42 ms 64884 KB Output is correct
14 Correct 45 ms 64892 KB Output is correct
15 Correct 44 ms 64872 KB Output is correct
16 Correct 49 ms 64916 KB Output is correct
17 Correct 43 ms 64992 KB Output is correct
18 Correct 41 ms 64916 KB Output is correct
19 Correct 41 ms 64980 KB Output is correct
20 Correct 39 ms 64972 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 64880 KB Output is correct
2 Correct 178 ms 64932 KB Output is correct
3 Correct 165 ms 64984 KB Output is correct
4 Correct 151 ms 64928 KB Output is correct
5 Correct 168 ms 64980 KB Output is correct
6 Correct 173 ms 64972 KB Output is correct
7 Correct 162 ms 64976 KB Output is correct
8 Correct 159 ms 64936 KB Output is correct
9 Correct 155 ms 64908 KB Output is correct
10 Correct 167 ms 64980 KB Output is correct
11 Execution timed out 3065 ms 65040 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 64868 KB Output is correct
2 Correct 183 ms 64972 KB Output is correct
3 Correct 156 ms 64968 KB Output is correct
4 Correct 159 ms 64976 KB Output is correct
5 Correct 185 ms 64992 KB Output is correct
6 Correct 174 ms 64976 KB Output is correct
7 Correct 206 ms 64932 KB Output is correct
8 Correct 189 ms 64900 KB Output is correct
9 Correct 154 ms 64972 KB Output is correct
10 Correct 170 ms 64972 KB Output is correct
11 Correct 550 ms 64976 KB Output is correct
12 Correct 575 ms 64980 KB Output is correct
13 Correct 581 ms 64980 KB Output is correct
14 Correct 621 ms 64976 KB Output is correct
15 Correct 528 ms 64972 KB Output is correct
16 Correct 571 ms 64980 KB Output is correct
17 Correct 580 ms 64984 KB Output is correct
18 Correct 600 ms 64980 KB Output is correct
19 Correct 560 ms 64972 KB Output is correct
20 Correct 562 ms 64976 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64980 KB Output is correct
2 Correct 30 ms 64972 KB Output is correct
3 Correct 31 ms 64884 KB Output is correct
4 Correct 34 ms 64972 KB Output is correct
5 Correct 32 ms 64992 KB Output is correct
6 Correct 28 ms 64968 KB Output is correct
7 Correct 30 ms 64976 KB Output is correct
8 Correct 29 ms 64908 KB Output is correct
9 Correct 33 ms 64980 KB Output is correct
10 Correct 30 ms 64980 KB Output is correct
11 Correct 42 ms 64948 KB Output is correct
12 Correct 43 ms 64956 KB Output is correct
13 Correct 42 ms 64884 KB Output is correct
14 Correct 45 ms 64892 KB Output is correct
15 Correct 44 ms 64872 KB Output is correct
16 Correct 49 ms 64916 KB Output is correct
17 Correct 43 ms 64992 KB Output is correct
18 Correct 41 ms 64916 KB Output is correct
19 Correct 41 ms 64980 KB Output is correct
20 Correct 39 ms 64972 KB Output is correct
21 Correct 159 ms 64880 KB Output is correct
22 Correct 178 ms 64932 KB Output is correct
23 Correct 165 ms 64984 KB Output is correct
24 Correct 151 ms 64928 KB Output is correct
25 Correct 168 ms 64980 KB Output is correct
26 Correct 173 ms 64972 KB Output is correct
27 Correct 162 ms 64976 KB Output is correct
28 Correct 159 ms 64936 KB Output is correct
29 Correct 155 ms 64908 KB Output is correct
30 Correct 167 ms 64980 KB Output is correct
31 Execution timed out 3065 ms 65040 KB Time limit exceeded
32 Halted 0 ms 0 KB -