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;
}