oj.uz

Submission #635497

# Submission time Handle Problem Language Result Execution time Memory
635497 2022-08-26T10:39:37 Z Cyanmond Party (INOI20_party) C++17
7 / 100
 3000 ms 35820 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 = 1500000;
std::array<i64, width> pa, pb, pc;

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);
    pc[0] = 1;
    const i64 v2 = mul(pb.back(), v1);
    for (int i = 1; i < width; ++i) pc[i] = mul(pc[i - 1], v2);
}

std::unordered_map<i64, i64> p2memo;

i64 pow2(i64 n) {
    const i64 v1 = n / (width * width);
    i64 ret = pc[v1];
    n -= width * width * v1;
    const i64 v2 = n / width;
    mul_m(ret, pb[v2]);
    n -= width * v2;
    return mul(ret, pa[n]);
}

void solve() {
    // Time Complexity O(log^4 N)
    i64 N;
    std::cin >> N;
    // N = 2 ^ k - 1
    i64 k = 0;
    while ((1ll << k) - 1 < N) ++k;
    // assert((1ll << k) - 1 == N);
 
    std::vector<i64> red_vs = {N};
    while (red_vs.back() != 1) {
        red_vs.push_back(red_vs.back() / 2);
    }
    std::reverse(red_vs.begin(), red_vs.end());
 
    std::vector<std::vector<i64>> red_count_vs(k);
    for (int i = k - 1; i >= 0; --i) {
        red_count_vs[i].assign(k - i, 0);
        red_count_vs[i][0] = 1;
        for (int j = 1; j < k - i; ++j) red_count_vs[i][j] += red_count_vs[i + 1][j - 1];
        if (i != k - 1 and red_vs[i + 1] == 2 * red_vs[i] + 1) {
            for (int j = 1; j < k - i; ++j) red_count_vs[i][j] += 1ll << (j - 1);
        } else {
            for (int j = 1; j < k - i - 1; ++j) red_count_vs[i][j] += 1ll << (j - 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;
            for (int u = 0; u <= 2 * k; ++u) {
                i64 count_v = 0;
                for (i64 p = 0; p <= u; ++p) {
                    const i64 now_d = d - p;
                    if (now_d < 0) continue;
                    const i64 t = u - p;
                    if (now_d + t >= k) continue;
                    
                    if (t == 0) ++count_v;
                    else {
                        if (p == 0) count_v += red_count_vs[now_d][t];
                        else count_v += red_count_vs[now_d][t] - red_count_vs[now_d + 1][t - 1];
                    }
                }
                if (count_v == 0) continue;
                add_m(ret, mul(u, add(pow2(N - sum), mod - pow2(N - sum - count_v))));
                sum += count_v;
            }
        } else {
            // no rec
            i64 v2 = v;
            for (int fd = d; fd < k; ++fd) {
                if (v * (1ll << (fd - d)) > N) continue;
                const i64 ms = nmr(1ll << (fd - d));
                i64 sum = 0;
                for (int u = 0; u <= fd + k; ++u) {
                    i64 count_v = 0;
                    bool h = false;
 
                    for (int p = 0; p <= std::min(u, fd); ++p) {
                        const int now_d = fd - p;
                        bool th = false;
                        if (red_vs[now_d] == v2 / (1ll << p)) th = true;
                        const int t = u - p;
                        if (now_d + t >= k) {
                            if (th) h = true;
                            continue;
                        }
 
                        if (th) {
                            if (t == 0) ++count_v;
                            else {
                                if (h) count_v += red_count_vs[now_d][t] - red_count_vs[now_d + 1][t - 1];
                                else count_v += red_count_vs[now_d + 1][t - 1];
                            }
                            h = true;
                        } else {
                            if (v % 2 == 1 and now_d + t == k - 1) continue;
                            count_v += 1ll << (p != 0 and t != 0 ? t - 1 : t);
                        }
                    }
                    if (count_v == 0) continue;
                    add_m(ret, mul(mul(ms, u), add(pow2(N - sum), mod - pow2(N - sum - count_v))));
                    sum += count_v;
                }
                v2 *= 2;
            }
        }
 
        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();
    int Q;
    std::cin >> Q;
    while (Q--) solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35404 KB Output is correct
2 Correct 39 ms 35396 KB Output is correct
3 Correct 35 ms 35448 KB Output is correct
4 Correct 33 ms 35524 KB Output is correct
5 Correct 35 ms 35404 KB Output is correct
6 Correct 33 ms 35532 KB Output is correct
7 Correct 33 ms 35404 KB Output is correct
8 Correct 34 ms 35432 KB Output is correct
9 Correct 34 ms 35404 KB Output is correct
10 Correct 34 ms 35432 KB Output is correct
11 Correct 70 ms 35544 KB Output is correct
12 Correct 60 ms 35532 KB Output is correct
13 Correct 57 ms 35424 KB Output is correct
14 Correct 60 ms 35536 KB Output is correct
15 Correct 56 ms 35532 KB Output is correct
16 Correct 57 ms 35532 KB Output is correct
17 Correct 61 ms 35476 KB Output is correct
18 Correct 67 ms 35536 KB Output is correct
19 Correct 59 ms 35660 KB Output is correct
20 Correct 67 ms 35476 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2052 ms 35816 KB Output is correct
2 Correct 2370 ms 35672 KB Output is correct
3 Correct 2103 ms 35564 KB Output is correct
4 Correct 1707 ms 35676 KB Output is correct
5 Correct 2205 ms 35696 KB Output is correct
6 Correct 2119 ms 35700 KB Output is correct
7 Correct 1903 ms 35820 KB Output is correct
8 Correct 1970 ms 35576 KB Output is correct
9 Correct 1895 ms 35576 KB Output is correct
10 Correct 2063 ms 35564 KB Output is correct
11 Execution timed out 3057 ms 35540 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1871 ms 35564 KB Output is correct
2 Correct 2162 ms 35568 KB Output is correct
3 Correct 1808 ms 35576 KB Output is correct
4 Correct 1911 ms 35568 KB Output is correct
5 Correct 2230 ms 35700 KB Output is correct
6 Correct 2131 ms 35804 KB Output is correct
7 Correct 2069 ms 35680 KB Output is correct
8 Correct 2240 ms 35700 KB Output is correct
9 Correct 1957 ms 35572 KB Output is correct
10 Correct 2169 ms 35576 KB Output is correct
11 Execution timed out 3078 ms 35544 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35404 KB Output is correct
2 Correct 39 ms 35396 KB Output is correct
3 Correct 35 ms 35448 KB Output is correct
4 Correct 33 ms 35524 KB Output is correct
5 Correct 35 ms 35404 KB Output is correct
6 Correct 33 ms 35532 KB Output is correct
7 Correct 33 ms 35404 KB Output is correct
8 Correct 34 ms 35432 KB Output is correct
9 Correct 34 ms 35404 KB Output is correct
10 Correct 34 ms 35432 KB Output is correct
11 Correct 70 ms 35544 KB Output is correct
12 Correct 60 ms 35532 KB Output is correct
13 Correct 57 ms 35424 KB Output is correct
14 Correct 60 ms 35536 KB Output is correct
15 Correct 56 ms 35532 KB Output is correct
16 Correct 57 ms 35532 KB Output is correct
17 Correct 61 ms 35476 KB Output is correct
18 Correct 67 ms 35536 KB Output is correct
19 Correct 59 ms 35660 KB Output is correct
20 Correct 67 ms 35476 KB Output is correct
21 Correct 2052 ms 35816 KB Output is correct
22 Correct 2370 ms 35672 KB Output is correct
23 Correct 2103 ms 35564 KB Output is correct
24 Correct 1707 ms 35676 KB Output is correct
25 Correct 2205 ms 35696 KB Output is correct
26 Correct 2119 ms 35700 KB Output is correct
27 Correct 1903 ms 35820 KB Output is correct
28 Correct 1970 ms 35576 KB Output is correct
29 Correct 1895 ms 35576 KB Output is correct
30 Correct 2063 ms 35564 KB Output is correct
31 Execution timed out 3057 ms 35540 KB Time limit exceeded
32 Halted 0 ms 0 KB -