oj.uz

Submission #635662

# Submission time Handle Problem Language Result Execution time Memory
635662 2022-08-26T15:34:36 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 65108 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 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 28 ms 64940 KB Output is correct
2 Correct 28 ms 64912 KB Output is correct
3 Correct 32 ms 64900 KB Output is correct
4 Correct 32 ms 64924 KB Output is correct
5 Correct 32 ms 64908 KB Output is correct
6 Correct 32 ms 64956 KB Output is correct
7 Correct 29 ms 64980 KB Output is correct
8 Correct 29 ms 64980 KB Output is correct
9 Correct 29 ms 64844 KB Output is correct
10 Correct 29 ms 64932 KB Output is correct
11 Correct 43 ms 64992 KB Output is correct
12 Correct 39 ms 65016 KB Output is correct
13 Correct 40 ms 64988 KB Output is correct
14 Correct 49 ms 64936 KB Output is correct
15 Correct 41 ms 64980 KB Output is correct
16 Correct 40 ms 64888 KB Output is correct
17 Correct 38 ms 64896 KB Output is correct
18 Correct 38 ms 64972 KB Output is correct
19 Correct 38 ms 64912 KB Output is correct
20 Correct 46 ms 65068 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 64980 KB Output is correct
2 Correct 189 ms 64976 KB Output is correct
3 Correct 166 ms 64900 KB Output is correct
4 Correct 152 ms 64980 KB Output is correct
5 Correct 169 ms 64980 KB Output is correct
6 Correct 162 ms 64964 KB Output is correct
7 Correct 150 ms 64868 KB Output is correct
8 Correct 168 ms 64912 KB Output is correct
9 Correct 156 ms 64972 KB Output is correct
10 Correct 163 ms 64936 KB Output is correct
11 Execution timed out 3062 ms 65108 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 65024 KB Output is correct
2 Correct 174 ms 64904 KB Output is correct
3 Correct 154 ms 64980 KB Output is correct
4 Correct 157 ms 64996 KB Output is correct
5 Correct 180 ms 64892 KB Output is correct
6 Correct 175 ms 64896 KB Output is correct
7 Correct 172 ms 64860 KB Output is correct
8 Correct 181 ms 64928 KB Output is correct
9 Correct 160 ms 64972 KB Output is correct
10 Correct 170 ms 64984 KB Output is correct
11 Correct 537 ms 64892 KB Output is correct
12 Correct 528 ms 64940 KB Output is correct
13 Correct 530 ms 64972 KB Output is correct
14 Correct 536 ms 64980 KB Output is correct
15 Correct 548 ms 64980 KB Output is correct
16 Correct 520 ms 64972 KB Output is correct
17 Correct 558 ms 64884 KB Output is correct
18 Correct 543 ms 64972 KB Output is correct
19 Correct 534 ms 64980 KB Output is correct
20 Correct 550 ms 64980 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 64940 KB Output is correct
2 Correct 28 ms 64912 KB Output is correct
3 Correct 32 ms 64900 KB Output is correct
4 Correct 32 ms 64924 KB Output is correct
5 Correct 32 ms 64908 KB Output is correct
6 Correct 32 ms 64956 KB Output is correct
7 Correct 29 ms 64980 KB Output is correct
8 Correct 29 ms 64980 KB Output is correct
9 Correct 29 ms 64844 KB Output is correct
10 Correct 29 ms 64932 KB Output is correct
11 Correct 43 ms 64992 KB Output is correct
12 Correct 39 ms 65016 KB Output is correct
13 Correct 40 ms 64988 KB Output is correct
14 Correct 49 ms 64936 KB Output is correct
15 Correct 41 ms 64980 KB Output is correct
16 Correct 40 ms 64888 KB Output is correct
17 Correct 38 ms 64896 KB Output is correct
18 Correct 38 ms 64972 KB Output is correct
19 Correct 38 ms 64912 KB Output is correct
20 Correct 46 ms 65068 KB Output is correct
21 Correct 169 ms 64980 KB Output is correct
22 Correct 189 ms 64976 KB Output is correct
23 Correct 166 ms 64900 KB Output is correct
24 Correct 152 ms 64980 KB Output is correct
25 Correct 169 ms 64980 KB Output is correct
26 Correct 162 ms 64964 KB Output is correct
27 Correct 150 ms 64868 KB Output is correct
28 Correct 168 ms 64912 KB Output is correct
29 Correct 156 ms 64972 KB Output is correct
30 Correct 163 ms 64936 KB Output is correct
31 Execution timed out 3062 ms 65108 KB Time limit exceeded
32 Halted 0 ms 0 KB -