AtCoder Beginner Contest 180

发表于2020-10-23更新于2023-09-17字数统计1.3k阅读时长12分作者Shane

比赛链接

F Unbranched

Description

nn 个不同的点 mm 条边构成一张图，满足图中每个连通块要么是环（无自环），要么是链，且最大的联通块的大小恰好为 ll，问这样的图有多少个。

Solution

先考虑这样一个问题：

  • 求将 {1,2,...,n}\left\{ 1,2,...,n \right\} 分组，每组不空的方案数。

这个问题可以用 dpdp 求解。设 dp[i]dp[i] 表示将 ii 个数分组的方案数，那么有 dp[i]=∑j=0i−1dp[j]∗Ci−1i−1−jdp[i] = \sum\limits_{j=0}^{i-1}dp[j]*C_{i-1}^{i-1-j}。这里可以理解为从前 i−1i-1 个数中选 i−j−1i-j-1 个数和 ii 凑成一组，再对剩下的 jj 个数分组。时间复杂度为 O(n2)O(n^2)。


进一步考虑：

  • 求将 {1,2,...,n}\left\{ 1,2,...,n \right\} 分组，最大的一组大小恰好为 ll (1≤l≤n1\le l \le n) 的方案数。

容易想到设 dp[i][j]dp[i][j] 表示将前 ii 个数分组，最大的一组大小恰为 jj 的方案数。那么有 dp[i][max(sz,i−j)]=∑j=max(0,i−l)i−1dp[j][sz]∗Ci−1i−1−j,sz∈[0,min(l,j)]dp[i][max(sz,i-j)] = \sum\limits_{j=max(0,i-l)}^{i-1}dp[j][sz]*C_{i-1}^{i-1-j},sz ∈ [0,min(l,j)]，最后答案为 dp[n][l]dp[n][l]。该解法时间复杂度为 O(n3)O(n^3)，可以优化。

设 dp[i][j]dp[i][j] 表示将前 ii 个数分组，最大的一组大小不超过 jj 的方案数，易得状态转移方程 dp[i][l]=∑j=max(0,i−l)i−1dp[j][l]∗Ci−1i−1−jdp[i][l] = \sum\limits_{j=max(0,i-l)}^{i-1}dp[j][l]*C_{i-1}^{i-1-j}，那么让最大组大小恰为 ll 的方案数为 dp[i][l]−dp[i][l−1]dp[i][l]-dp[i][l-1]。这里第二维实际上是多余的。设大小限制为 kk, 那么 dp[i]=∑j=max(0,i−k)i−1dp[j]∗Ci−1i−1−jdp[i] = \sum\limits_{j=max(0,i-k)}^{i-1}dp[j]*C_{i-1}^{i-1-j}，因此对 k=lk=l 和 k=l−1k=l-1 的情况分别做一次 dpdp 将答案相减即可。时间复杂度为 O(n2)O(n^2)。


回到本题，这题其实就是在前一个问题的基础上加上了边数限制和组内部的顺序问题。由于有 mm 条边，因此一定会构成 n−mn-m 条链（一个点也算链的情况），其余的都是大小至少为 2 的环。设 dp[i][j]dp[i][j] 表示将 ii 个点构成一个由 jj 条链组成，最大连通块大小不超过 ll 的图方案数。对于一个新的状态，要么增加一条链，要么增加一个环，同时还要乘上构成指定长度的链或环的方案数。其中，n(n≥2)n(n \ge 2) 个不同的点构成一条链的方案数为 n!/2n!/2，n(n≥3)n(n \ge 3) 个不同的点构成一个环的方案数为 (n−1)!/2(n-1)!/2。对于大小限制为 l−1l-1 的情况可类似处理，时间复杂度为 O(n3)O(n^3)。

Code

Unbranched
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 303;
const int MOD = 1E9 + 7;
int n, m, l;
LL dp[MAXN][MAXN], chainNum[MAXN], cycleNum[MAXN], C[MAXN][MAXN];

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void add(LL& a, LL b) { a = (a + b) % MOD; }

void init() {
    for (int i = 0; i <= 300; i++) C[i][0] = 1;
    for (int i = 1; i <= 300; i++)
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    chainNum[1] = chainNum[2] = 1;
    for (int i = 3; i <= 300; i++) chainNum[i] = chainNum[i - 1] * i % MOD;
    cycleNum[2] = cycleNum[3] = 1;
    for (int i = 4; i <= 300; i++)
        cycleNum[i] = cycleNum[i - 1] * (i - 1) % MOD;
}

int solve(int n, int l, int m) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int p = i - l; p <= i - 1; p++) {
            for (int chain = max(0, n - m - (n - p)); chain <= min(p, n - m);
                 chain++) {//注意剩下 n - p 个点不可能构成超过 n - p 条链
                add(dp[i][chain], dp[p][chain] * C[i - 1][i - p - 1] % MOD *
                                      cycleNum[i - p] % MOD);
                add(dp[i][chain + 1], dp[p][chain] * C[i - 1][i - p - 1] % MOD *
                                          chainNum[i - p] % MOD);
            }
        }
    return dp[n][n - m];
}

signed main() {
    init();
    read(n, m, l);
    cout << ((solve(n, l, m) - solve(n, l - 1, m)) % MOD + MOD) % MOD;
    return 0;
}