BEST定理学习笔记

发表于

内容：

对于一张有向图，以 ss 为起点，它的欧拉回路数量为

detsdegs!∏(degu−1)![u≠s]det_sdeg_s!\prod (deg_u-1)![u \neq s]

detsdet_s 表示以 ss 为根的有根生成树个数 (可以是内向树也可以是外向树), degudeg_u 表示点 uu 的度数（可以是入度也可以是出度).

证明：

对于一棵有根生成树，不妨设它是内向树，给它的每一条边标一个顺序，其中指向根的边顺序最靠后，方案数显然是 degs!∏(degu−1)![u≠s]deg_s!\prod (deg_u-1)![u \neq s], 再乘上有根生成树的个数就是 detsdegs!∏(degu−1)![u≠s]det_sdeg_s!\prod (deg_u-1)![u \neq s], 接着就是证明每种标号方案对应一条欧拉回路.

每经过一条边后，删掉这条边，只需证明剩下的边存在欧拉路径，即剩下的边满足如下条件。

  1. 图弱联通
  2. 有两个点入度和出度相差 11, 其它点入度等于出度

若删去的边 (u,v)(u, v) 是非树边，由于树边是每个点最后离开的边 (u,v)(u, v) 之间的树边一定还没有被删去，则 uu 到 vv 之间可以直接通过树边形成弱连通；

若删去的边是树边，则删去后 uu 与剩下的图完全断开，相当于删去了一条链末端的一条边，剩余边仍然弱连通。

所以删掉一条边后剩下的图仍然有欧拉路径.

Code:

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int mod = 1e6 + 3;

const int N = 110;
int A[N][N];
int degin[N], degout[N];
int T, n;
int fac[300000], inv[300000], ifac[300000];

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

int sub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

int det(int n) {
    int res = 1;
    for (int i = 2; i <= n; ++i) {
        if (!degout[i]) continue;
        if (!A[i][i]) {
            for (int j = i + 1; j <= n; ++j) {
                if (A[j][i]) {
                    swap(A[i], A[j]);
                    res = -res;
                    break;
                }
            }
        }
        for (int j = i + 1; j <= n; ++j) {
            int div = 1ll * A[j][i] * qpow(A[i][i], mod - 2) % mod;
            for (int k = i; k <= n; ++k) {
                A[j][k] = sub(A[j][k], 1ll * div * A[i][k] % mod);
            }
        }
    }
    res = (mod + res) % mod;
    for (int i = 2; i <= n; ++i) {
        res = 1ll * res * A[i][i] % mod;
    }
    return res;
}

signed main() {
    scanf("%d", &T);
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
    for (int i = 2; i <= 220000; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
    }
    while (T--) {
        scanf("%d", &n);
        memset(A, 0, sizeof(A));
        memset(degin, 0, sizeof(degin));
        memset(degout, 0, sizeof(degout));
        for (int i = 1; i <= n; ++i) {
            int s;
            scanf("%d", &s);
            for (int j = 1; j <= s; ++j) {
                int x;
                scanf("%d", &x);
                A[i][x] = sub(A[i][x], 1);
                ++degin[x];
                ++degout[i];
            }
            A[i][i] = add(A[i][i], s);
        }
        if (n == 1) {
            puts("1");
            continue;
        }
        int flag = 0;
        for (int i = 1; i <= n; ++i) {
            if (degin[i] != degout[i]) {
                flag = 1;
            }
        }
        if (flag == 1) {
            puts("0");
            continue;
        }
        int res = det(n);
        res = 1ll * res * fac[degout[1]] % mod;
        for (int i = 2; i <= n; ++i) {
            res = 1ll * res * fac[degout[i] - 1] % mod;
        }
        printf("%d\n", res);
    }
    return 0;
}