题解归档 - cf104118D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118D
• 本地来源：problems/cf104118D/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/D
• 原始标题：Gym 104118D - Domination Devil

思路

Gym 104118D - Domination Devil

Orient every remaining bridge from lower rank to higher rank. The condition is exactly:

• every vertex has outdegree at most k;
• the underlying undirected graph is connected.

Let

F_m = sum_{j=0..k} C(m,j).

For all legal graphs on n labeled ranks, vertex i independently chooses at most k outgoing edges among the n-i higher-ranked vertices, so

A_n = prod_{m=0}^{n-1} F_m.

Now use the standard labeled connected-component decomposition. The count of legal structures on a block depends only on its size, because only the relative order inside the block matters. Therefore, with exponential generating functions:

A(x) = exp(C(x))

where C_n is the number of connected legal graphs. Thus:

C(x) = log(A(x)).

Implementation:

1. Compute A_n.
2. Build EGF coefficients A_n / n!.
3. Take formal power series logarithm with NTT under 1699741697 = 1621 * 2^20 + 1.
4. Answer is [x^n] log(A(x)) * n!.

For F_m:

• if m <= k, F_m = 2^m;
• otherwise F_m = 2 F_{m-1} - C(m-1,k).

Complexity: O(n log n).

Checks:

• official samples 1-4
• brute force for small n,k

代码

来源：problems/cf104118D/solution.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1699741697;

int mod_pow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

int primitive_root() {
    int factors[2] = {2, 1621}; // MOD - 1 = 2^20 * 1621
    for (int g = 2;; ++g) {
        bool ok = true;
        for (int q : factors) {
            if (mod_pow(g, (MOD - 1) / q) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}

void ntt(vector<int> &a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    static int G = primitive_root();
    for (int len = 2; len <= n; len <<= 1) {
        int wlen = mod_pow(G, (MOD - 1) / len);
        if (invert) wlen = mod_pow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            int half = len >> 1;
            for (int j = 0; j < half; ++j) {
                int u = a[i + j];
                int v = (int)(w * a[i + j + half] % MOD);
                int x = (u >= MOD - v ? u - (MOD - v) : u + v);
                int y = u - v;
                if (y < 0) y += MOD;
                a[i + j] = x;
                a[i + j + half] = y;
                w = w * wlen % MOD;
            }
        }
    }

    if (invert) {
        int inv_n = mod_pow(n, MOD - 2);
        for (int &x : a) x = (ll)x * inv_n % MOD;
    }
}

vector<int> multiply(vector<int> a, vector<int> b, int need = -1) {
    if (a.empty() || b.empty()) return {};
    int total = (int)a.size() + (int)b.size() - 1;
    if (need != -1) total = min(total, need);
    if (1LL * a.size() * b.size() <= 200000) {
        vector<int> c(total);
        for (int i = 0; i < (int)a.size(); ++i) {
            if (!a[i]) continue;
            int upto = min((int)b.size(), total - i);
            for (int j = 0; j < upto; ++j) {
                c[i + j] = (c[i + j] + (ll)a[i] * b[j]) % MOD;
            }
        }
        return c;
    }
    int n = 1;
    while (n < (int)a.size() + (int)b.size() - 1) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; ++i) a[i] = (ll)a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(total);
    return a;
}

vector<int> poly_inv(const vector<int> &f, int n) {
    vector<int> r(1, mod_pow(f[0], MOD - 2));
    for (int m = 2; (m >> 1) < n; m <<= 1) {
        vector<int> a(min((int)f.size(), m));
        for (int i = 0; i < (int)a.size(); ++i) a[i] = f[i];
        vector<int> t = multiply(a, r, m);
        t.resize(m);
        t[0] = (2 - t[0] + MOD) % MOD;
        for (int i = 1; i < m; ++i) {
            if (t[i]) t[i] = MOD - t[i];
        }
        r = multiply(r, t, m);
        r.resize(m);
    }
    r.resize(n);
    return r;
}

vector<int> poly_log(const vector<int> &f, const vector<int> &inv_int, int n) {
    vector<int> der(max(0, n - 1));
    for (int i = 1; i < n; ++i) der[i - 1] = (ll)f[i] * i % MOD;
    vector<int> invf = poly_inv(f, n);
    vector<int> q = multiply(der, invf, n - 1);
    q.resize(max(0, n - 1));
    vector<int> res(n);
    for (int i = 1; i < n; ++i) res[i] = (ll)q[i - 1] * inv_int[i] % MOD;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> fact(n + 1), ifact(n + 1), inv(n + 1), pow2(n + 1);
    fact[0] = ifact[0] = pow2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (ll)fact[i - 1] * i % MOD;
        pow2[i] = (ll)pow2[i - 1] * 2 % MOD;
    }
    ifact[n] = mod_pow(fact[n], MOD - 2);
    for (int i = n; i >= 1; --i) ifact[i - 1] = (ll)ifact[i] * i % MOD;
    for (int i = 1; i <= n; ++i) inv[i] = (ll)fact[i - 1] * ifact[i] % MOD;

    auto C = [&](int nn, int rr) -> int {
        if (rr < 0 || rr > nn) return 0;
        return (ll)fact[nn] * ifact[rr] % MOD * ifact[nn - rr] % MOD;
    };

    vector<int> total(n + 1), egf(n + 1);
    total[0] = 1;
    int ways = 1; // F_0
    for (int sz = 1; sz <= n; ++sz) {
        int m = sz - 1; // number of greater-ranked possible neighbors for the new lowest vertex
        if (m == 0) ways = 1;
        else if (m <= k) ways = pow2[m];
        else {
            ways = (2LL * ways - C(m - 1, k)) % MOD;
            if (ways < 0) ways += MOD;
        }
        total[sz] = (ll)total[sz - 1] * ways % MOD;
    }

    for (int i = 0; i <= n; ++i) egf[i] = (ll)total[i] * ifact[i] % MOD;

    // Let C(x)=log(E(x)), where E(x)=sum total[n] x^n/n!.
    // E(x) C'(x) = E'(x).
    // If d[i] = i * [x^i]C(x), then:
    // d[t] + sum_{i=1}^{t-1} d[i] * egf[t-i] = t * egf[t].
    vector<int> rhs(n + 1), d(n + 1);
    for (int i = 1; i <= n; ++i) rhs[i] = (ll)i * egf[i] % MOD;

    function<void(int, int)> cdq = [&](int l, int r) {
        if (l == r) {
            d[l] = rhs[l];
            return;
        }
        int mid = (l + r) >> 1;
        cdq(l, mid);

        vector<int> a(mid - l + 1), b(r - l);
        for (int i = l; i <= mid; ++i) a[i - l] = d[i];
        for (int j = 1; j <= r - l; ++j) b[j - 1] = egf[j];
        vector<int> c = multiply(a, b, r - l);
        for (int t = mid + 1; t <= r; ++t) {
            int sub = c[t - l - 1];
            rhs[t] -= sub;
            if (rhs[t] < 0) rhs[t] += MOD;
        }

        cdq(mid + 1, r);
    };

    cdq(1, n);
    int connected_egf_n = (ll)d[n] * inv[n] % MOD;
    cout << (ll)connected_egf_n * fact[n] % MOD << '\n';
    return 0;
}