oj.uz

Submission #635671

# Submission time Handle Problem Language Result Execution time Memory
635671 2022-08-26T16:01:36 Z Cyanmond Party (INOI20_party) C++17
40 / 100
 3000 ms 65084 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) % (mod - 1);
                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) % (mod - 1);
                    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 34 ms 64928 KB Output is correct
2 Correct 30 ms 64956 KB Output is correct
3 Correct 29 ms 64980 KB Output is correct
4 Correct 30 ms 64896 KB Output is correct
5 Correct 29 ms 64880 KB Output is correct
6 Correct 29 ms 64952 KB Output is correct
7 Correct 31 ms 64848 KB Output is correct
8 Correct 32 ms 64976 KB Output is correct
9 Correct 30 ms 64952 KB Output is correct
10 Correct 30 ms 64980 KB Output is correct
11 Correct 45 ms 64984 KB Output is correct
12 Correct 42 ms 64972 KB Output is correct
13 Correct 41 ms 64984 KB Output is correct
14 Correct 42 ms 64972 KB Output is correct
15 Correct 44 ms 65008 KB Output is correct
16 Correct 42 ms 64972 KB Output is correct
17 Correct 43 ms 64972 KB Output is correct
18 Correct 41 ms 64980 KB Output is correct
19 Correct 42 ms 64900 KB Output is correct
20 Correct 43 ms 64924 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 64980 KB Output is correct
2 Correct 233 ms 64904 KB Output is correct
3 Correct 180 ms 64852 KB Output is correct
4 Correct 153 ms 64980 KB Output is correct
5 Correct 186 ms 64876 KB Output is correct
6 Correct 192 ms 64912 KB Output is correct
7 Correct 170 ms 64972 KB Output is correct
8 Correct 166 ms 64944 KB Output is correct
9 Correct 178 ms 64972 KB Output is correct
10 Correct 183 ms 64980 KB Output is correct
11 Execution timed out 3085 ms 64984 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 64856 KB Output is correct
2 Correct 177 ms 64884 KB Output is correct
3 Correct 166 ms 64916 KB Output is correct
4 Correct 184 ms 64948 KB Output is correct
5 Correct 182 ms 64968 KB Output is correct
6 Correct 184 ms 64956 KB Output is correct
7 Correct 190 ms 64876 KB Output is correct
8 Correct 179 ms 64984 KB Output is correct
9 Correct 180 ms 64972 KB Output is correct
10 Correct 243 ms 64976 KB Output is correct
11 Correct 599 ms 64980 KB Output is correct
12 Correct 585 ms 64900 KB Output is correct
13 Correct 608 ms 64924 KB Output is correct
14 Correct 642 ms 64976 KB Output is correct
15 Correct 594 ms 64968 KB Output is correct
16 Correct 597 ms 64868 KB Output is correct
17 Correct 573 ms 64980 KB Output is correct
18 Correct 579 ms 64980 KB Output is correct
19 Correct 613 ms 65084 KB Output is correct
20 Correct 575 ms 64928 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 64928 KB Output is correct
2 Correct 30 ms 64956 KB Output is correct
3 Correct 29 ms 64980 KB Output is correct
4 Correct 30 ms 64896 KB Output is correct
5 Correct 29 ms 64880 KB Output is correct
6 Correct 29 ms 64952 KB Output is correct
7 Correct 31 ms 64848 KB Output is correct
8 Correct 32 ms 64976 KB Output is correct
9 Correct 30 ms 64952 KB Output is correct
10 Correct 30 ms 64980 KB Output is correct
11 Correct 45 ms 64984 KB Output is correct
12 Correct 42 ms 64972 KB Output is correct
13 Correct 41 ms 64984 KB Output is correct
14 Correct 42 ms 64972 KB Output is correct
15 Correct 44 ms 65008 KB Output is correct
16 Correct 42 ms 64972 KB Output is correct
17 Correct 43 ms 64972 KB Output is correct
18 Correct 41 ms 64980 KB Output is correct
19 Correct 42 ms 64900 KB Output is correct
20 Correct 43 ms 64924 KB Output is correct
21 Correct 173 ms 64980 KB Output is correct
22 Correct 233 ms 64904 KB Output is correct
23 Correct 180 ms 64852 KB Output is correct
24 Correct 153 ms 64980 KB Output is correct
25 Correct 186 ms 64876 KB Output is correct
26 Correct 192 ms 64912 KB Output is correct
27 Correct 170 ms 64972 KB Output is correct
28 Correct 166 ms 64944 KB Output is correct
29 Correct 178 ms 64972 KB Output is correct
30 Correct 183 ms 64980 KB Output is correct
31 Execution timed out 3085 ms 64984 KB Time limit exceeded
32 Halted 0 ms 0 KB -