ARC165E 题解

First Post:

Last Update:

比较强的概率转化,如果没见过真的很难想。

原过程中,一个点被选的概率与当前 的连通块有关,根本做不得。

考虑进行转化,我们不妨允许找到一个所在连通块大小小于 的点进行切分,但是如果出现这种情况,我们定义这次操作不消耗时间,称其为“无效操作”。

容易发现,无效操作怎么做都不会影响有效操作的情况,而且每个有效操作的执行概率仍然是均等的。所以这个转化的正确性可以理解。

转化完之后,我们把每一步删去的点列出来,设 表示第 步删除的点。我们对所有排列 算贡献之和即可。

一个排列 中,如果位置 满足,当删到 时,其所属的连通块大小 ,那么这个位置就有 的贡献。

枚举 。假设我们可以枚举删到这个点时其所属的连通块 。设 的周围一圈的点集为 。那么删到 时连通块为 ,当且仅当所有 中的点都在 前被删,所有 中的点都在 后被删。因为我们只需算概率,所以只用考虑这 个点的相对位置,那么 之前的概率为 中第一个被删的概率为 。那么,删到 时连通块恰好为 的概率就是

于是我们只需对于每个 计算, 的连通块数即可。以 为根跑一遍树形背包即可,单次背包的复杂度为

所以总时间复杂度为

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int fac[N],ifac[N],inv[N];
inline void init(int n) {
fac[0] = 1;
for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
inv[1] = 1;
for(int i = 2;i <= n;i++) inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
ifac[0] = 1;
for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
}
inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
inline int invC(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * ifac[n] * fac[m] % P * fac[n - m] % P;}
int dp[N][N][N],sze[N]; // 选一个包含根的连通块,[根][内点][界点]
int n,K;
vector<int> G[N];

void DP(int x,int fa) {
static int tmp[N][N];
memset(tmp,0,sizeof tmp);
memset(dp[x],0,sizeof dp[x]);
dp[x][0][0] = 1;sze[x] = 0;
int cnt = 0;
for(auto y : G[x]) {
if(y == fa) continue;
DP(y,x);++cnt;
for(int a = 0;a <= sze[x];a++)
for(int b = 0;a + b <= sze[x];b++) {
Plus(tmp[a][b + 1],dp[x][a][b]); // 这个子树不选任何一个点
for(int c = 0;c <= sze[y];c++)
for(int d = 0;c + d <= sze[y];d++)
Plus(tmp[a + c][b + d],1ll * dp[x][a][b] * dp[y][c][d] % P);
}
sze[x] += sze[y];
for(int a = 0;a <= sze[x];a++)
for(int b = 0;a + b <= sze[x];b++)
dp[x][a][b] = tmp[a][b],tmp[a][b] = 0;
}
++sze[x];
for(int a = sze[x];a >= 1;a--)
for(int b = 0;a + b <= sze[x];b++)
dp[x][a][b] = dp[x][a - 1][b],dp[x][a - 1][b] = 0;
}
int Solve(int x) {
int res = 0;
DP(x,0);
for(int a = K + 1;a <= n;a++)
for(int b = 1;a + b <= n;b++) {
Plus(res,1ll * dp[x][a][b] * invC(a + b,a) % P * inv[a] % P);
}
return res;
}
int main() {
cin >> n >> K;
for(int i = 1,a,b;i < n;i++)
cin >> a >> b,G[a].push_back(b),G[b].push_back(a);
init(n);
int res = 1;
for(int i = 1;i <= n;i++) Plus(res,Solve(i));
cout << res << endl;
return 0;
}