oj.uz

Submission #635668

# Submission time Handle Problem Language Result Execution time Memory
635668 2022-08-26T15:55:21 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 65100 KB 
#include <bits/stdc++.h>
 
using i64 = long long;
 
constexpr int 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 ret2 = 0;
                i64 sum = 0, memo = pow2_N;
                int n = N % (mod - 1);
                for (int u = 0; u <= fd + k; ++u) {
                    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(ret2, u * add(memo, mod - new_memo));
                    sum += count_v;
                    memo = new_memo;
                    n = new_n;
                }
                ret2 %= mod;
                ret2 *= ms;
                ret += ret2;
            }
            ret %= mod;
        }
 
        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 31 ms 64980 KB Output is correct
2 Correct 35 ms 64908 KB Output is correct
3 Correct 29 ms 64964 KB Output is correct
4 Correct 29 ms 64956 KB Output is correct
5 Correct 29 ms 64916 KB Output is correct
6 Correct 30 ms 64984 KB Output is correct
7 Correct 29 ms 64880 KB Output is correct
8 Correct 32 ms 64980 KB Output is correct
9 Correct 31 ms 64848 KB Output is correct
10 Correct 31 ms 64948 KB Output is correct
11 Correct 43 ms 64996 KB Output is correct
12 Correct 45 ms 64980 KB Output is correct
13 Correct 43 ms 65100 KB Output is correct
14 Correct 42 ms 64908 KB Output is correct
15 Correct 42 ms 64992 KB Output is correct
16 Correct 43 ms 65008 KB Output is correct
17 Correct 39 ms 65012 KB Output is correct
18 Correct 45 ms 64980 KB Output is correct
19 Correct 43 ms 64880 KB Output is correct
20 Correct 43 ms 64988 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 64976 KB Output is correct
2 Correct 174 ms 64980 KB Output is correct
3 Correct 165 ms 64904 KB Output is correct
4 Correct 147 ms 64960 KB Output is correct
5 Correct 168 ms 65008 KB Output is correct
6 Correct 165 ms 64912 KB Output is correct
7 Correct 171 ms 64972 KB Output is correct
8 Correct 155 ms 64980 KB Output is correct
9 Correct 152 ms 64984 KB Output is correct
10 Correct 155 ms 64980 KB Output is correct
11 Execution timed out 3091 ms 64980 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 64980 KB Output is correct
2 Correct 166 ms 64904 KB Output is correct
3 Correct 187 ms 64956 KB Output is correct
4 Correct 156 ms 64952 KB Output is correct
5 Correct 179 ms 64856 KB Output is correct
6 Correct 198 ms 64944 KB Output is correct
7 Correct 175 ms 64972 KB Output is correct
8 Correct 184 ms 64940 KB Output is correct
9 Correct 157 ms 64888 KB Output is correct
10 Correct 168 ms 64980 KB Output is correct
11 Correct 517 ms 64968 KB Output is correct
12 Correct 529 ms 64972 KB Output is correct
13 Correct 512 ms 64960 KB Output is correct
14 Correct 526 ms 64928 KB Output is correct
15 Correct 540 ms 64868 KB Output is correct
16 Correct 526 ms 64980 KB Output is correct
17 Correct 525 ms 64972 KB Output is correct
18 Correct 523 ms 64980 KB Output is correct
19 Correct 551 ms 64980 KB Output is correct
20 Correct 524 ms 64980 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 64980 KB Output is correct
2 Correct 35 ms 64908 KB Output is correct
3 Correct 29 ms 64964 KB Output is correct
4 Correct 29 ms 64956 KB Output is correct
5 Correct 29 ms 64916 KB Output is correct
6 Correct 30 ms 64984 KB Output is correct
7 Correct 29 ms 64880 KB Output is correct
8 Correct 32 ms 64980 KB Output is correct
9 Correct 31 ms 64848 KB Output is correct
10 Correct 31 ms 64948 KB Output is correct
11 Correct 43 ms 64996 KB Output is correct
12 Correct 45 ms 64980 KB Output is correct
13 Correct 43 ms 65100 KB Output is correct
14 Correct 42 ms 64908 KB Output is correct
15 Correct 42 ms 64992 KB Output is correct
16 Correct 43 ms 65008 KB Output is correct
17 Correct 39 ms 65012 KB Output is correct
18 Correct 45 ms 64980 KB Output is correct
19 Correct 43 ms 64880 KB Output is correct
20 Correct 43 ms 64988 KB Output is correct
21 Correct 152 ms 64976 KB Output is correct
22 Correct 174 ms 64980 KB Output is correct
23 Correct 165 ms 64904 KB Output is correct
24 Correct 147 ms 64960 KB Output is correct
25 Correct 168 ms 65008 KB Output is correct
26 Correct 165 ms 64912 KB Output is correct
27 Correct 171 ms 64972 KB Output is correct
28 Correct 155 ms 64980 KB Output is correct
29 Correct 152 ms 64984 KB Output is correct
30 Correct 155 ms 64980 KB Output is correct
31 Execution timed out 3091 ms 64980 KB Time limit exceeded
32 Halted 0 ms 0 KB -