题解 P6017 【[CSGRound3]仙人掌】

· · 题解

前言

这是 CSGRound 3 的 E 题，在月赛上只有 4 个同学做出了此题，且在赛后没有人写题解。所以我在此发布官方题解。

做法1：

暴力枚举仙人掌，可以过第一个 subtask1。说不定加点剪枝可以过 subtask2。

做法2：

考虑把度数序列中所有元素放进一个 multiset，可以发现这样合法的 multiset 非常少，而每一个合法的 multiset 对应的所有的度数序列都是合法的。 所以可以用园方树进行 dp，这样可以过 subtask1,subtask2。或许可以过 subtask3。

做法3：

对于一棵树的情况，只要所有点度数都至少为 1 且和为 2n-2 即可，所以答案直接可以用组合数算。

做法4：

对于 n=m 的情况，发现只要度数为 1 的点不超过 n-2 即可，所以直接组合数算。

做法5：

考虑什么情况下仙人掌能构造出来。 定义一个函数

f(n)=\lbrack n \mod 2=0 \rbrack (\frac{3}{2}n-2)+\lbrack n \mod 2=1\rbrack (\frac{3}{2}(n-1))

即 n 个点仙人掌边数的上界。 可以发现当度数均为偶数时，度数序列合法当且仅当边数（度数和/2）m 满足 n\le m\le f(n)。

大致证明如下： 如果边数不在这个范围内，显然不合法。 如果度数和正好等于 2n，那么可以直接连一个大环。 否则一定存在 3 个点使得他们度数和大于 6，那么可以将这三个点连一个环，然后视为缩成一个点。 都是偶数的情况可以把再连的环边集中到一个点上。

那么之前的条件依然满足，问题变成了一个形式相同，规模更小的子问题，可以归纳证明。 对于存在奇数的情况，可以发现如果合法那么一定存在一种不连环的方案使得把它缩点之后变成全是偶数的情况，且在偶数的情况下合法。

那么消奇数的过程每连一条边就相当于度数和减少 2，节点数减少 1，可以发现我们只需要使这样的边连得尽量少。那么可以奇数的点两两连边，但是可以发现，如果度数为 1 的点特别多可能会出问题，因为消完之后出现度数为 0 的点了，这时候我们只能把度数为 1 的点两两挂到度数大的偶数点上了。 所以度数序列是否合法只和点数，度数和，奇数度数点的个数，度数为 1 的点的个数有关，可以直接 dp 加点优化，可以过 subtask1,2,3，可能能过 subtask4。

做法6：

用组合数优化做法5，可以直接AC。

remark:

subtask7 出题人暂时想不到特殊做法,如果又会做法的可以私信出题人。

Code

#include <cstdio>
#include <algorithm>
#define mo 998244353
using namespace std;
int C[5005][5005];
bool check(int n, int m, int a, int b) {
    if (m == n - 1)
        return 1;
    if (a > b)
        m -= a, n -= a;
    else
        m -= (a + b) >> 1, n -= (a + b) >> 1;
    if (m < n)
        return 0;
    if (m > (n - 1) / 2 * 3 + (n - 1) % 2)
        return 0;
    return 1;
}
int main() {
    int cas;
    scanf("%d", &cas);
    C[0][0] = 1;
    for (int i = 1; i <= 5000; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;
    }
    while (cas--) {
        int n, m;
        scanf("%d%d", &n, &m);
        if (m > (n - 1) / 2 * 3 + (n - 1) % 2) {
            puts("0");
            continue;
        }
        if (n == 1) {
            puts("0");
            continue;
        }
        if (n == 2) {
            if (m == 1)
                puts("1");
            else
                puts("0");
            continue;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n - i; j++) {
                if (i + j * 3 > m + m)
                    continue;
                if (!check(n, m, i, j))
                    continue;
                int m1 = m + m - i - j, n1 = n - i;
                if (m1 & 1)
                    continue;
                ans = ((long long)C[m1 / 2 - 1][n1 - 1] * C[n][n1] % mo * C[n1][j] + ans) % mo;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

注：在此给出验题人的代码。