[ABC253Ex] We Love Forest Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个点无边的图，给定 $m$$m$ 条待选的无向边。每次等概率地从 $m$$m$ 条边中抽取一条边加入图中。 $n-1$$n - 1$ 次询问求加 $1,2,\cdots ,n-1$$1, 2, \cdots, n - 1$ 次边后原图形成一个森林（一棵树亦为森林）的概率为多少。对 $998244353$$998244353$ 取模。

Solution

考虑 FZT，即子集计数，具体可参考 FZT - 子集计数学习笔记 或 [ABC213G] Connectivity 2 Solution，发现本题与 ABC213G 相似。

因为本题存在选的边数的限制，所以不难想到需要在一般 FZT 的状态中额外添加一维记录。

状态类比 ABC213G，较为显然，令 $F(i,S)$$F(i, S)$ 表示选了 $i$$i$ 条边，点集状态为 $S$$S$ 形成的森林数。令 $G(S)$$G(S)$ 表示点集状态为 $S$$S$ 生成树的总方案数。

首先考虑如何处理 $G(S)$$G(S)$，发现这个东西就是个裸的矩阵树定理。不过也可以通过枚举子集设计转移来实现，令 $cnt(S,T)$$cnt(S, T)$ 表示点集 $S$$S$ 和点集 $T$$T$ 之间的边数，方程不难想到为：

然后发现这个东西有重复，不难想到重复分为两种，一种是因为 $T$$T$ 和 $S\oplus T$$S \oplus T$ 对调之后属于相同方案而被重复统计了，这个可以通过钦定一个点解决，或者在最终答案乘一个 ${\displaystyle \frac{1}{2}}$$\dfrac{1}{2}$ 解决。另一种是因为我们的转移，是通过将两个树形结构通过之间的边拼接在一起来实现的，而这种情况也可以认为是将一棵完整的树通过断开某一条边然后分别计算子树，这样的话对于一棵确定的树断开每条边都是等价的，所以会重复边数次，也就是答案需要乘一个 ${\displaystyle \frac{1}{|S|-1}}$$\dfrac{1}{\lvert S \rvert - 1}$，故可以考虑将转移改为：

或：

然后初始值大概是 $G(2^k)=1$$G(2^k) = 1$。

不难发现如果无脑处理 $cnt$$cnt$ 的话复杂度是 $O(2^{2n}m)$$O(2^{2n}m)$，显然寄，于是考虑优化，令 $cnte(S)$$cnte(S)$ 表示点集 $S$$S$ 中的边数，不难想到对于 $cnt$$cnt$ 可以如下容斥：

则预处理 $cnte$$cnte$ 的复杂度为 $O(m{2}^n)$$O(m2^n)$，$cnt$$cnt$ 可以 $O(1)$$O(1)$ 求解，$G$$G$ 的处理则是 $O(3^n)$$O(3^n)$ 的。

然后矩阵树定理的结论大概就是首先对这个图建出拉普拉斯矩阵 $L$$L$，然后答案就是 $det(L_0)$$\det(L_0)$，其中 $L_0$$L_0$ 表示 $L$$L$ 去掉第 $i$$i$ 行第 $i$$i$ 列的子矩阵，其中 $i$$i$ 任意。具体证明参考 矩阵树定理（Matrix-tree Theorem）笔记。所以只需要矩阵建出来无脑求一下行列式即可。

于是考虑如何转移 $F$$F$，依然类比 ABC213G，我们令 $|S|$$\lvert S \rvert$ 表示点集 $S$$S$ 中点的数量，也就是 __builtin_popcount(S)，不难发现转移：

也就是钦定一个子集为一棵树，然后剩下的作为森林，钦定 $1$$1$ 节点在树中可以去重，具体在 ABC213G 也有说明。

不过很遗憾这个又是错的。我们在 ABC213G 中钦定 $1$$1$ 是因为 $1$$1$ 一定被选，但是在本题里并没有这个限制，所以我们要换一种写法，不难想到使用 $S$$S$ 中的最后一个 $1$$1$ 是易于实现且正确的，即 $\mathrm{lowbit}(S)$$\operatorname{lowbit}(S)$，或者说 $S\wedge -S$$S \land -S$。于是转移改为：

边界条件的话就是如果 $S$$S$ 的点数恰好为 $i+1$$i + 1$，那么显然就是一棵树，即 $F(i,S)=G(S)$$F(i, S) = G(S)$。

然后考虑答案，令 $Smx=2^n-1$$Smx = 2^n - 1$，即全集，不难想到对于选 $i$$i$ 条边的答案 $an{s}_i$$ans_i$ 有：

也不难理解，概率转计数，总方案数为 $m_i$$m_i$，然后要让所有点形成森林，方案中选择的 $i$$i$ 条边任意排列均不同，所以需要在乘一个 $i!$$i!$。

大概就这样了，处理 $G$$G$ 的复杂度为 $O(n^3{2}^n)$$O(n^3 2^n)$，处理 $F$$F$ 的复杂度为 $O(n{3}^n)$$O(n 3^n)$，处理答案复杂度作为常数，最终复杂度 $O((m+n^3)2^n+3^n)$$O((m + n^3) 2^n + 3^n)$，可以通过。

Code

xxxxxxxxxx
105
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MAX_STATUS (20000)
23
#define MOD (ll)(998244353)
24
#define EXIST(x) (S & (1 << ((x) - 1)))
25

26
template < typename T = int >
27
inline T read(void);
28

29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[1100];
34
ROPNEW(ed);
35
Edge* head[20];
36

37
int N, M;
38
int deg[20];
39
ll G[MAX_STATUS], F[20][MAX_STATUS];
40
int cnte[MAX_STATUS];
41
ll fact[30];
42

43
int lowbit(int x){return x & -x;}
44
int CalCnt(int S, int T){return cnte[S | T] - cnte[S] - cnte[T];}
45
ll qpow(ll a, ll b){
46
    ll ret(1), mul(a);
47
    while(b){
48
        if(b & 1)ret = ret * mul % MOD;
49
        b >>= 1;
50
        mul = mul * mul % MOD;
51
    }return ret;
52
}
53

54
int main(){fact[0] = 1;
55
    for(int i = 1; i <= 20; ++i)fact[i] = fact[i - 1] * i % MOD;
56
    N = read(), M = read();
57
    const int Smx = (1 << N) - 1;
58
    for(int i = 1; i <= M; ++i){
59
        int s = read(), t = read();
60
        head[s] = new Edge{head[s], t};
61
        head[t] = new Edge{head[t], s};
62
    }
63
    for(int S = Smx; S; S = (S - 1) & Smx){
64
        int cnt(0);
65
        for(int p = 1; p <= N; ++p)
66
            for(auto i = head[p]; i; i = i->nxt)
67
                if(EXIST(p) && EXIST(SON))++cnt;
68
        cnt >>= 1;
69
        cnte[S] = cnt;
70
    }
71
    for(int S = 1; S <= Smx; ++S){
72
        if(__builtin_popcount(S) == 1){G[S] = 1; continue;}
73
        for(int T = (S - 1) & S; T; T = (T - 1) & S)
74
            if(T & lowbit(S))
75
                (G[S] += G[T] * G[S ^ T] % MOD * CalCnt(T, S ^ T) % MOD) %= MOD;
76
        (G[S] *= qpow(__builtin_popcount(S) - 1, MOD - 2)) %= MOD;
77
    }
78
    for(int i = 0; i <= N - 1; ++i)
79
        for(int S = 0; S <= Smx; ++S){
80
            if(__builtin_popcount(S) == i + 1){F[i][S] = G[S]; continue;}
81
            for(int T = (S - 1) & S; T; T = (T - 1) & S)
82
                if(T & lowbit(S) && i - (__builtin_popcount(T) - 1) >= 0)
83
                    (F[i][S] += G[T] * F[i - (__builtin_popcount(T) - 1)][S ^ T]) %= MOD;
84
        }
85
    for(int i = 1; i <= N - 1; ++i)
86
        printf("%lld\n", F[i][Smx] * fact[i] % MOD * qpow(qpow(M, i), MOD - 2) % MOD);
87
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88
    return 0;
89
}
90

91
template < typename T >
92
inline T read(void){
93
    T ret(0);
94
    int flag(1);
95
    char c = getchar();
96
    while(c != '-' && !isdigit(c))c = getchar();
97
    if(c == '-')flag = -1, c = getchar();
98
    while(isdigit(c)){
99
        ret *= 10;
100
        ret += int(c - '0');
101
        c = getchar();
102
    }
103
    ret *= flag;
104
    return ret;
105
}

UPD

update-2022_12_07 初稿