Submission #635481

#	Time	Username	Problem	Language	Result	Execution time	Memory
635481		Cyanmond	Party (INOI20_party)	C++17	7 / 100	3109 ms	788512 KiB

Main

#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);
}

std::array<i64, 100> p2m;

void init_p2() {
    p2m[0] = 2;
    for (int i = 0; i < 90; ++i) p2m[i + 1] = mul(p2m[i], p2m[i]);
}

std::unordered_map<i64, i64> p2memo;

i64 pow2(i64 n) {
    // if (p2memo.find(n) != p2memo.end()) return p2memo[n];
    i64 ret = 1;
    int i = 0;
    while (n != 0) {
        if (n & 1) mul_m(ret, p2m[i]);
        ++i;
        n >>= 1;
    }
    // return p2memo[n2] = ret;
    return ret;
}

std::vector<std::tuple<i64, i64, int>> evs;

void solve(const i64 N, const int q_id) {
    // Time Complexity O(log^4 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;
                const i64 ks = u;
                evs.push_back({N - sum, ks, q_id});
                evs.push_back({N - sum - count_v, -ks, q_id});
                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;
                    const i64 ks = mul(ms, u);
                    evs.push_back({N - sum, ks, q_id});
                    evs.push_back({N - sum - count_v, -ks, q_id});
                    sum += count_v;
                }
                v2 *= 2;
            }
        }

        return ret;
    };
    const auto res = dfs(dfs, 0, 1);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    init_p2();
    int Q;
    std::cin >> Q;
    std::vector<i64> invs(Q);
    for (int i = 0; i < Q; ++i) {
        i64 N; std::cin >> N;
        solve(N, i);
        invs[i] = inv(add(pow2(N), mod - 1));
    }

    std::sort(evs.begin(), evs.end());
    std::vector<i64> answer(Q);
    i64 now_v = 1, last = 0;
    for (const auto &[t, k, i] : evs) {
        mul_m(now_v, pow2(t - last));
        add_m(answer[i], mul(now_v, nmr(k)));
        last = t;
    }

    for (int i = 0; i < Q; ++i) std::cout << mul(answer[i], invs[i]) << std::endl;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(i64, int)':
Main.cpp:165:16: warning: unused variable 'res' [-Wunused-variable]
  165 |     const auto res = dfs(dfs, 0, 1);
      |                ^~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37