Solution Set【2024.1.21】

User-Unauthorized / 2024-01-21 / 原文

[MtOI2018] 情侣？给我烧了！

设 $f_{k, n}$ 表示在有 $n$ 对情侣的情况下钦定 $k$ 对情侣是和睦的方案数，$g_{k, n}$ 表示在有 $n$ 对情侣的情况下恰好有 $k$ 对情侣是和睦的方案数。考察二者之间的关系，我们有：

\[f_{k, n} = \sum\limits_{m = k}^{n} \dbinom{m}{k} g_{m, n} \]

根据二项式反演，我们有：

\[g_{k, n} = \sum\limits_{m = k}^{n} \left(-1\right)^{m - k} \dbinom{m}{k} f_{m, n} \]

考虑如何求出 $f_{k, n}$，我们有：

\[f_{k, n} = \dbinom{n}{k} \times n^{\underline k} \times 2^k \times \left(2n - 2k\right)! \]

上述式子的含义是：首先从 $n$ 对情侣中选出 $k$ 对情侣，然后将这 $k$ 对情侣钦定为和睦的，然后将这 $k$ 对情侣的位置确定下来，最后将剩下的 $2n - 2k$ 个人的位置确定下来。

代入上述关系式，我们有：

\[\begin{aligned} g_{k, n} =& \sum\limits_{m = k}^{n} \left(-1\right)^{m - k} \dbinom{m}{k} \times \dbinom{n}{m} \times n^{\underline m} \times 2^m \times \left(2n - 2m\right)! \\ =& \sum\limits_{m = k}^{n} \left(-1\right)^{m - k} \frac{m!}{k! \left(m - k\right)!} \times \frac{n!}{m!\left(n - m\right)!} \times \frac{n!}{\left(n - m\right)!} \times 2^m \times \left(2n - 2m\right)! \\ =& \frac{\left(n!\right)^2}{k!} \sum\limits_{m = k}^{n} \left(-1\right)^{m - k} \frac{2^m}{\left(m - k\right)!} \times \left(\frac{1}{\left(n - m\right)!}\right)^2 \times \left(2n - 2m\right)! \\ \end{aligned}\]

取 $i = m - k$，我们有：

\[\begin{aligned} g_{k, n} =& \frac{\left(n!\right)^2}{k!} \sum\limits_{i = 0}^{n - k} \left(-1\right)^{i} \frac{2^{k + i}}{i!} \times \left(\frac{1}{\left(n - k - i\right)!}\right)^2 \times \left(2n - 2k - 2i\right)! \\ =& \frac{2^k\left(n!\right)^2}{k!} \sum\limits_{i = 0}^{n - k} \left(-1\right)^{i} \frac{2^{i}}{i!} \times \left(\frac{1}{\left(n - k - i\right)!}\right)^2 \times \left(2n - 2k - 2i\right)! \\ \end{aligned}\]

记 $h_{m} = \sum\limits_{i = 0}^{m} \left(-1\right)^{i} \frac{2^{i}}{i!} \times \left(\frac{1}{\left(m - i\right)!}\right)^2 \times \left(2m - 2i\right)!$，我们有：

\[g_{k, n} = \frac{2^k\left(n!\right)^2}{k!} h_{n - k} \]

设 $N = \max n$，我们可以在 $\mathcal{O}(N^2)$ 的时间内预处理出 $h_{m}$ 的值，然后在 $\mathcal{O}(1)$ 的时间内求出 $g_{k, n}$ 的值。

复杂度为 $\mathcal{O}(N^2 + \sum n)$。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

namespace MODINT_WITH_FIXED_MOD {
    constexpr valueType MOD = 998244353;

    template<typename T1, typename T2>
    void Inc(T1 &a, T2 b) {
        a = a + b;

        if (a >= MOD)
            a -= MOD;
    }

    template<typename T1, typename T2>
    void Dec(T1 &a, T2 b) {
        a = a - b;

        if (a < 0)
            a += MOD;
    }

    template<typename T1, typename T2>
    T1 sum(T1 a, T2 b) {
        return a + b >= MOD ? a + b - MOD : a + b;
    }

    template<typename T1, typename T2>
    T1 sub(T1 a, T2 b) {
        return a - b < 0 ? a - b + MOD : a - b;
    }

    template<typename T1, typename T2>
    T1 mul(T1 a, T2 b) {
        return (long long) a * b % MOD;
    }

    template<typename T1, typename T2>
    void Mul(T1 &a, T2 b) {
        a = (long long) a * b % MOD;
    }

    template<typename T1, typename T2>
    T1 pow(T1 a, T2 b) {
        T1 result = 1;

        while (b > 0) {
            if (b & 1)
                Mul(result, a);

            Mul(a, a);
            b = b >> 1;
        }

        return result;
    }
} // namespace MODINT_WITH_FIXED_MOD

using namespace MODINT_WITH_FIXED_MOD;

class BinomialCoefficient {
private:
    valueType N;
    ValueVector _Fact, _InvFact;

public:
    BinomialCoefficient() = default;

    BinomialCoefficient(valueType n) : N(n), _Fact(N + 1, 1), _InvFact(N + 1, 1) {
        for (valueType i = 1; i <= N; ++i)
            _Fact[i] = mul(_Fact[i - 1], i);

        _InvFact[N] = pow(_Fact[N], MOD - 2);

        for (valueType i = N - 1; i >= 0; --i)
            _InvFact[i] = mul(_InvFact[i + 1], i + 1);
    }

    valueType operator()(valueType n, valueType m) {
        if (n < 0 || m < 0 || n < m)
            return 0;

        if (m > N)
            throw std::out_of_range("BinomialCoefficient::operator() : m > N");

        if (n <= N)
            return mul(_Fact[n], mul(_InvFact[m], _InvFact[n - m]));

        valueType result = 1;

        for (valueType i = 0; i < m; ++i)
            Mul(result, n - i);

        Mul(result, _InvFact[m]);

        return result;
    }

    valueType Fact(valueType n) {
        if (n < 0)
            return 0;

        if (n > N)
            throw std::out_of_range("BinomialCoefficient::Fact : n > N");

        return _Fact[n];
    }

    valueType InvFact(valueType n) {
        if (n < 0)
            return 0;

        if (n > N)
            throw std::out_of_range("BinomialCoefficient::InvFact : n > N");

        return _InvFact[n];
    }
};

constexpr valueType V = 1000;

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

    valueType T;

    std::cin >> T;

    BinomialCoefficient C(2 * V);

    ValueVector H(V + 1);

    ValueVector Pow2(V + 1, 0);

    Pow2[0] = 1;
    for (valueType i = 1; i <= V; ++i)
        Pow2[i] = mul(Pow2[i - 1], 2);

    for (valueType i = 0; i <= V; ++i) {
        for (valueType j = 0; j <= i; ++j) {
            if (j & 1)
                Dec(H[i], mul(mul(C.InvFact(j), Pow2[j]), mul(mul(C.InvFact(i - j), C.InvFact(i - j)), C.Fact(2 * i - 2 * j))));
            else
                Inc(H[i], mul(mul(C.InvFact(j), Pow2[j]), mul(mul(C.InvFact(i - j), C.InvFact(i - j)), C.Fact(2 * i - 2 * j))));
        }
    }

    for (valueType testcase = 0; testcase < T; ++testcase) {
        valueType N;

        std::cin >> N;

        ValueVector G(N + 1, 0);

        for (valueType i = 0; i <= N; ++i)
            G[i] = mul(mul(C.Fact(N), C.Fact(N)), mul(mul(C.InvFact(i), Pow2[i]), H[N - i]));

        for (valueType i = 0; i <= N; ++i)
            std::cout << G[i] << '\n';
    }

    std::cout << std::flush;

    return 0;
}

[HAOI2015] 按位或

考虑 Min-Max 容斥，我们有：

\[E\left(\max\limits_{x \in S} x\right) = \sum\limits_{T \subseteq S} \left(-1\right)^{\left\lvert T \right\rvert - 1} E\left(\min\limits_{x \in T} x\right) \]

设全集为 $U$，我们要求的便是 $E\left(\max\limits_{x \in U} x\right)$。那么我们考虑对于每个集合 $S$ 求出 $E\left(\min\limits_{x \in S} x\right)$。

考虑 $E\left(\min\limits_{x \in S} x\right)$ 的意义，即 $S$ 中至少有一个元素被选中的期望步数，考虑其中至少一个元素被选中的概率，我们有：

\[E\left(\min\limits_{x \in S} x\right) = \dfrac{1}{\sum\limits_{T \cap S \neq \varnothing} P(T)} \]

其中 $P(T)$ 表示 $T$ 所代表的二进制数出现的概率。

考虑如何计算 $\sum\limits_{T \cap S \neq \varnothing} P(T)$，正难则反，我们考虑计算 $\sum\limits_{T \cap S = \varnothing} P(T)$，即 $S$ 中的元素都没有被选中的概率。发现我们有：

\[T \cap S = \varnothing \Leftrightarrow T \subseteq \complement_U S \]

因此对 $P$ 序列做高维前缀和即可。复杂度为 $\mathcal{O}(n2^n)$。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef long double realType;
typedef std::vector<realType> RealVector;

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

    valueType N;

    std::cin >> N;

    valueType const M = 1 << N;

    RealVector P(M);

    for (valueType i = 0; i < M; ++i)
        std::cin >> P[i];

    for (valueType i = 0; i < N; ++i) {
        for (valueType j = 0; j < M; ++j) {
            if ((j >> i) & 1)
                P[j] += P[j ^ (1 << i)];
        }
    }

    realType ans = 0;

    for (valueType s = 1; s < M; ++s) {
        if (__builtin_popcount(s) & 1) {
            ans += static_cast<realType>(1) / static_cast<realType>(1 - P[(M - 1) ^ s]);
        } else {
            ans -= static_cast<realType>(1) / static_cast<realType>(1 - P[(M - 1) ^ s]);
        }
    }

    if (std::isinf(ans) || std::isnan(ans))
        std::cout << "INF" << std::endl;
    else
        std::cout << std::fixed << std::setprecision(10) << ans << std::endl;

    return 0;
}