跃迁引擎启动

ZOJ4069 Sub-cycle Graph

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

题面

求 $n$ 个点 $m$ 条边的带标号图是某个 $n$ 个点的环的子图的个数。

分析

把几个情况特判掉：

  1. $m>n$：图上已经有环。
  2. $m=n$：图本身就是一个 $n$ 个点的环，答案为 ${n!\over2}$。
  3. $m=0$：答案为 $1​$（底下的公式会挂在这个地方）。

题目等价于求将一个带标号的图分成 $n-m$ 条链的方案数（块内有序，块间无序）。

先给块间加一个有序条件，最后乘上 $n! \over (n-m)!​$ 即可去除掉块间的序，因此可以使用指数生成函数先算出块内块间有序的方案数。

考虑一条链的情况，只有一个点时，方案数为 $1$，有 $n$ 个点时 $(n \ge 2)$，方案数为 $n! \over 2$。因此得到对应的指数生成函数
$$
\begin{array}{}
f(x)&=&x+{2! \over 2}{x^2 \over 2!}+{3! \over 2}{x^3 \over 3!}+\dots \
&=&x+{1\over2}x^2+{1\over2}x^3+\dots \
&=&{x\over 2}+{1\over2}x(1+x+x^2+x^3+\dots) \
&=&{x\over 2}+{1\over2}{x \over 1-x}
\end{array}
$$
答案为
$$
\begin{array}{}
ans&=&{n! \over (n-m)!}[x^n]({x\over 2}+{1\over 2}{x \over 1-x})^{n-m} \
&=&{n! \over (n-m)!}[x^n]({x \over 2}(1+{1 \over 1-x}))^{n-m} \
&=&{n! \over (n-m)!2^{n-m}}[x^n]x^{n-m}(1+{1 \over 1-x})^{n-m} \
&=&{n! \over (n-m)!2^{n-m}}[x^m](1+{1 \over 1-x})^{n-m} \
&=&{n! \over (n-m)!2^{n-m}}[x^m]\sum_{i=0}^{n-m} {n-m \choose i} ({1 \over 1-x})^i \
&=&{n! \over (n-m)!2^{n-m}}[x^m]\sum_{i=0}^{n-m} {n-m \choose i} (1+x+x^2+\dots)^i \
&=&{n! \over (n-m)!2^{n-m}}\sum_{i=0}^{n-m} {n-m \choose i}{m+i-1 \choose m} \
\end{array}
$$

终于把现场留下的泪补了？

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 500000 + 5;

ll qpow(ll x, ll n = mod - 2) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return r;
}

int f[maxn], inv[maxn], finv[maxn];
void init(){
    inv[1] = 1;
    for (int i = 2; i < maxn; i++) inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
    f[0] = finv[0] = 1; 
    for (int i = 1; i < maxn; i++) {
        f[i] = f[i - 1] * 1ll * i % mod;
        finv[i] = finv[i - 1] * 1ll * inv[i] % mod;
    }
}
int C(int n, int m){
    if (m < 0 || m > n) return 0;
    return f[n] * 1ll * finv[n - m] % mod * finv[m] % mod;
}

int n, m;
ll a[maxn], b[maxn];

int main(){
    init();
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d%d", &n, &m);
        if (m > n) {
            puts("0"); continue;
        }
        if (m == n) {
            printf("%lld\n", 1ll * f[n - 1] * inv[2] % mod); continue;
        }
        if (m == 0) {
            puts("1"); continue;
        }
        ll ans = 0;
        for (int i = 0; i <= n - m; i++) {
            ans = (ans + 1ll * C(n - m, i) * C(m + i - 1, m)) % mod;
        }
        printf("%lld\n", ans * f[n] % mod * finv[n - m] % mod * qpow(inv[2], n - m) % mod);
    }
    return 0;
}