CTime_Pup_314

不能再颓废了

0%

[[CSGRound3]仙人掌]题解

发表于 更新于 分类于 阅读次数： Valine：

这道题考完之后一直也没题解，蒟蒻就自己找了些资料，一知半解地写了这道题，主要参考 NERC2019 C.Cactus Revenge 和 Cactus graph realization of degree sequence，接下来的事情也主要复读这两个资料的

我们在之后的讨论中设度数序列为 \(d\)，图的点集大小为 \(n\)，边集大小为 \(m\)，首先有个很明显的性质即 \[ \sum_{i=1}^nd_i=2m \]

首先考虑树的情况，树的情况很好猜，一个度数序能构成树的充要条件即

\[ \sum_{i=1}^nd_i=2(n-1)\land \forall i,d_i\ge1 \]

考虑归纳证明，首先 \(n=2\) 是 \(d_1=d_2=1\) 两者互相连边即可，结论显然成立

对于 \(n>2\)，若 \(\forall i,d_i\ge2\)，则 \(\sum_{i=1}^nd_i\ge2n\) 所以一定有 j，满足 \(d_j=1\)，我们将 \(j\) 与剩下任意一个 \(k,d_k\ge2\) 连边，将 \(d_j\) 和 \(d_k\) 减 \(1\)，将 \(j\) 删去，得到新的度数序 \(d'\)，那么由于 \(d'\) 是可以构成树的，所以 \(d\) 也可以

接着我们考虑边仙人掌的情况

我们任取图的一个生成树，每条非树边都仅代表一个环，所以环数 \(c\) 显然满足 \[ c=m-(n-1)\in[0,\lfloor\frac{n-1}{2}\rfloor] \]

若度数都为偶数，分两种情况，都为 \(2\) 时，我们只需要构成一个大环即可，否则我们其中一定存在相异的 \(u\) 和 \(v\) 满足 \(d_u=d_v=2\)（可以用树的反证法说明)，我们令 \(u\) 和 \(v\) 与另一个 \(w,d_w\ge4\) 构成一个三元环，与树同理构造出 \(d'\)，这是 \(d'\) 满足 \(c-1\le\lfloor\frac{n-3}{2}\rfloor\)，于是可以归纳证明

若度数不全为偶数，则显然奇数个数为偶数并且我们需要找到更强的约束条件，考虑割边的个数为 \(b\)，奇数个数为 \(o\)，叶子个数为 \(l\)，对于 \(b\)，满足 \(b\ge\max(\frac{o}{2},l)\)，所以对 \(c\) 有更强的约束为

\[ c\le\lfloor\frac{n-1-\max(\frac{o}{2},l)}{2}\rfloor\le\lfloor\frac{n-1-b}{2}\rfloor \]

首先对于一些平凡的情况，若序列满足上述条件即可构造出仙人掌，对于剩下的分两种情况考虑当 \(l\ge1\) 时我们从度数最大的点 \(u\) 向叶子 \(v\) 连边，构造出 \(d'\) 这时 \(d'\) 满足 \(c\le\lfloor\frac{n-1-\max(\frac{o-1-k}{2},l-1)}{2}\rfloor,k\le1\) 成立，我们从度数最大的点 \(u\) 向度数最小的 \(v\) 和 \(w\) 构成三元环，与上面同理可证成立

所以我们就得到判断度数序列是否可以构成仙人掌的条件

计数就很简单了，我们考虑枚举 \(o\) 和 \(l\)，用组合数计算出不定方程 \[ \sum_{i=1}^nd_i=2m \]

其中满足有 \(o-l\) 个 \(d_i\) 不小于 \(3\) 且为奇数，\(l\) 个 \(d_i\) 为 \(1\)，\(n-o\) 个 \(d_i\) 为不小于 \(2\) 且为偶数的解的方案数

这里我不太会用隔板法算，所以用生成函数暴力算很显然我们要求出的就是

\[ [x^{2m-l}]\binom{n}{o}\binom{o}{l}(\frac{1}{1-x^2}-1)^{n-o}(\frac{x}{1-x^2}-x)^{o-l} \]

将后面的多项式展开就不多赘述了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 6e3+5, P = 998244353;
int t, n, m, c; int64 C[N][N], ans;
int main()
{ 
    for(int i = 0, n = 6e3; i <= n; ++i)
    {
        C[i][0] = 1;
        for(int j = 1; j <= i; ++j)
            C[i][j] = (C[i-1][j-1]+C[i-1][j])%P;
    }
    t = read();
    while(t--)
    {
        n = read(), m = read(), c = m-(n-1), ans = 0;
        if(0 <= c&&c <= (n-1)/2) 
            for(int o = 0; o <= n; o += 2)
                for(int l = 0; l <= o; ++l)
                {
                    int b = max(o/2, l), i = (2*m-2*n-o+2*l)/2;
                    if(c <= (n-1-b)/2) ans = (ans+C[n][o]*C[o][l]%P*C[n-l+i-1][i]%P)%P;
                }
        printf("%lld\n", ans);
    }
    return 0;
}

这道题应该属于图的可视化问题，这类问题常用这样的归纳证明，欲了解更多可以参照Graph realization problem 或这道题 CF1091E