[ARC106F] Figures 题解

标签：right const 题解 ARC106F T1 Figures left mod MOD

题意

给定 \(N\) 个带有若干洞的节点，其中第 \(i\) 个点上有 \(d_i\) 个洞。

先可以在两个不同的节点的洞之间连边，一个洞最多连一条边，求使得最终形成的图是一棵树的方案数，对 \(998244353\) 取模。

洞之间相互区分，两个方案不同当且仅当存在一条边在两个方案中的连的洞不同。

• \(2 \le N \le 2 \times 10^5\)
• \(1 \le d_i < 998244353\)

题解

首先设 \(S = \sum d_i\)，那么首先考虑 \(S \ge 2 \left(N - 1\right)\) 的情况，即一定有解的情况。

考虑组成一棵树的过程，可以从每个节点的父边入手，考虑对于每个节点，钦定一个特殊洞，使得其连向父亲节点。

那么我们每次操作可以转化为选择一个特殊洞，再选择一个非特殊洞，使得其相连。

可以发现每次操作后联通块数量一定会减少，在仅剩 \(2\) 个联通块时我们可以使其两个特殊洞相连，进而确定方案。因此我们只需要操作 \(N - 2\) 次。

考虑如何计算方案数。首先钦定特殊洞的方案数显然为 \(\prod d_i\)。对于第 \(i\) 次选择，我们可以从 \(N - i + 1\) 个特殊洞中选择一个，从 \(S - N - i + 1\) 个非特殊洞中选择一个，因此方案数为 \(\left(N - i + 1\right) \times \left(S - N - i + 1\right)\)。

因此可以得出总方案数：

\[\prod d_i \times \prod\limits_{i = 1}^{N - 2} \left(N - i + 1\right) \times \left(S - N - i + 1\right) \]

即

\[\prod d_i \times \prod\limits_{i = 0}^{N - 3} \left(S - N - i\right) \times N^{\underline{N - 2}} \]

发现每个节点被选择的顺序是不影响最终的方案的，但是被计算了多次，考虑除去这个影响。

因此最终答案为：

\[\prod d_i \times \prod\limits_{i = 0}^{N - 3} \left(S - N - i\right) \]

可以发现，若 \(S < 2 \left(N - 1\right)\)，那么上式的值一定为 \(0\)，于实际相符，因此直接计算上式的值即可。

Code

#include <bits/stdc++.h>

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

namespace MODINT {
    constexpr valueType MOD = 998244353;

    template<typename T1, typename T2, typename T3 = valueType>
    void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
        a = a + b;

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

    template<typename T1, typename T2, typename T3 = valueType>
    void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
        a = a - b;

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

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

    template<typename T1, typename T2, typename T3 = valueType>
    T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
        return a - b < 0 ? a - b + mod : a - b;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
        return (long long) a * b % mod;
    }

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

    template<typename T1, typename T2, typename T3 = valueType>
    T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
        T1 result = 1;

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

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

        return result;
    }

    constexpr valueType Inv2 = (MOD + 1) / 2;
}// namespace MODINT

using namespace MODINT;

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

    valueType N;

    std::cin >> N;

    valueType ans = 1, S = 0;

    ValueVector D(N);

    for (auto &iter : D) {
        std::cin >> iter;

        Mul(ans, iter);

        Inc(S, iter);
    }

    for (valueType i = 0; i <= N - 3; ++i)
        Mul(ans, sub(S, N + i));

    std::cout << ans << std::endl;

    return 0;
}

标签：right,const,题解,ARC106F,T1,Figures,left,mod,MOD
From： https://www.cnblogs.com/User-Unauthorized/p/solution-ARC106F.html