题解：P6017 [CSGRound3] 仙人掌

· · 题解

特判 n<3 的 corner。枚举仙人掌上有 a 个点的度数为 1，b 个点的度数大于 1 且为奇数（显然 a+b 就是仙人掌上度数为奇数的点数，需要满足 2\mid a+b）。考虑类比忘了哪个题的做法，先数一下度数排列的数量，先选 a 个度数为 1 的点 \binom na 然后再从剩下 n-a 个点里选 b 个度数为奇数的点 \binom{n-a}b，剩下点度数全都是至少为 2 的偶数，简单组合计数可得总贡献为 \binom na\binom{n-a}b\binom{m-\frac{a+b}2}{n-a-1}。

然后考虑怎么判度数序列是否可以组成仙人掌。这个东西考虑给奇数度数点配对，如果两个点度数至少一个不为 1 那么就可以连一条桥边然后合并成一个大的偶数度数点，可以贪心的让匹配后度数为 1 的点数量尽量少。记缩掉的点的数量为 t=\max(a,\frac{a+b}2) 则新图中有 n-t 个点 m-t 条边和 m-n+1 个简单环。因为 k 个环至少需要 2k+1 个点因此只需要满足 n-t\ge 2k+1 就可以构造出合法的仙人掌。然后在考虑 n 个点的仙人掌的边数上下界，显然下界是 n-1，上界随便画几个图就可以发现是 n+\lfloor\frac{n-3}2\rfloor。因此合并一下就得到了合法的充要条件。直接枚举 a,b 判定合法然后组合计数可以做到 O(n^2)。看着就很能优化但是我懒得想了。

namespace lowspeed_song {

mt19937_64 mt(time(0));

int fac[N], inv[N], ifac[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int n, m; cin >> n >> m;
    if (m > n + (n - 3) / 2 || m < n - 1) cout << 0 << '\n';
    else {
        if (!n) cout << 0 << '\n';
        else if (n == 1) {
            if (!m) cout << 1 << '\n';
            else cout << 0 << '\n';
        } else if (n == 2) {
            if (m == 1) cout << 1 << '\n';
            else cout << 0 << '\n';
        } else {
            int res = 0;
            for (int i = 0; i < n; ++i)
                for (int j = (i & 1); j <= n - i; j += 2) {
                    int rmv = max(i, (i + j) / 2);
                    if (n - rmv >= 2 * (m - n + 1) + 1) {
                        int nn = n - i, nm = m - (i + j) / 2;
                        if (nn <= nm) addmod(res, binom(n, i) * binom(nn, j) % mod * binom(nm - 1, nn - 1) % mod);
                    }
                }
            cout << res << '\n';
        }
    }
}

} // namespace lowspeed_song