Codeforces
1097G. Vladislav and a Great Legend
当时不会做
题意
给定一棵 \(n\) 个点的树
对于每个非空的点集 \(X\subseteq
\{1,2,\dotsc,n\}\)，定义 \(f(X)\) 表示最少的能让点集 \(X\) 联通的边的数量
求
\[
\sum_{X\subseteq \{1,2,\dotsc,n\},X\ne \varnothing} (f(X))^k
\]
模 \(10^9+7\)
\(n\le 10^5,k\le 200\)
做法
先考虑 \(X\)
是树上一个联通子树的点集怎么做
令 \(f_{i,j}\) 表示以 \(i\) 为根的子树，选择了 \(i\) 的所有方案的边数的 \(j\) 次和
直接二项式展开，合并两个子树是 \(\mathcal
O(k^2)\) 的，总复杂度 \(\mathcal
O(nk^2)\) 无法通过此题
考虑令 \(f_{i,j}\) 表示以 \(i\) 为根的子树，选择了 \(i\) 的所有方案的边数的 \(j\) 阶下降幂的和
对于下降幂我们有
\[
\begin{align}
(x+1)^{\underline n} & = n! \binom{x+1}{n} \\
& = n!\left(\binom{x}{n}+\binom{x}{n-1}\right) \\
& = x^{\underline n} + n\times x^{\underline {n-1}}
\end{align}
\]
\[
\begin{align}
(x+y)^{\underline n} & = n! \binom{x+y}{n} \\
& = n! \sum_{i=0}^n \binom{x}{i} \binom{y}{n-i} \\
& = n! \sum_{i=0}^n \frac{x^{\underline i}}{i!} \times
\frac{y^{\underline {n-i}}}{(n-i)!} \\
& = \sum_{i=0}^n \binom{n}{i} x^{\underline i} y^{\underline {n-i}}
\end{align}
\]
因此我们可以 \(\mathcal O(k)\)
地加入一条边和 \(\mathcal O(k^2)\)
地合并两个子树
总复杂度还是 \(\mathcal O(nk^2)\)
的，无法通过
由于下降幂的性质，当以 \(i\)
为根的子树中的点数不大于 \(j\)
时，\(f_{i,j}=0\)
我们可以记 \(size_i\) 表示以 \(i\) 为根的子树的点数，每次合并严格 \(\mathcal O(min\{size_x, k\}, min\{size_y,
k\})\) 地合并两个子树 \(x,
y\)，注意不能包含 \(min\{size_x,k\}^2\)
合并两个相邻子树 \(x,y\)
时，我们选出 \(x\) 的子树中 dfs
序最大的 \(k\) 个点和 \(y\) 的子树中 dfs 序最小的 \(k\) 个点，这样每个点最多会对前后 \(2k\) 个点形成贡献，于是总复杂度是 \(\mathcal O(nk)\)
最后用斯特林数
\[
x^k = \sum_{i=0}^k
\begin{Bmatrix} k \\ i \end{Bmatrix}
x^{\underline{i}}
\]
复原出 \(k\) 次幂和即可
接下来考虑不是联通子树的情况
定义叶子是联通子树上度为 \(1\)
的点，可以发现一个联通子树需要计算 \(2^a\) 次，其中 \(a\) 是非叶子数量
统计 \(i\)
处的答案时，若方案包含了至少两个 \(i\)
的儿子， \(i\) 就不是叶子，则需要乘系数
\(2\)，这可以全部计算，最后减去只含一个儿子的情况
做完 \(i\)
之后，只要方案包含了至少一个儿子，由于 \(i\) 的父亲必须选择，\(i\) 就不是叶子，因此把除了 \(i\) 单个点的方案都乘 \(2\) 即可
代码
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
| #include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 100005, K = 202, P = 1000000007;
int n, k, num, Ans, ans[K], p[K], C[K][K], S[K][K], siz[N], h[N], e[N<<1], pre[N<<1], f[N][K];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
void dfs(int u, int fa=0){
f[u][0]=1;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa){
dfs(e[i], u), siz[u]+=siz[e[i]];
for(int j=min(siz[u], k); j; --j){
f[e[i]][j]=(f[e[i]][j]+(ll)f[e[i]][j-1]*j)%P;
ans[j]=(ans[j]-f[e[i]][j]+P)%P;
}
++f[e[i]][0];
for(int j=min(siz[u], k); ~j; --j){
f[u][j]=(ll)f[u][j]*f[e[i]][0]%P;
for(int t=max(j-siz[e[i]], 0); t<j && t<=siz[u]-siz[e[i]]; ++t)
f[u][j]=(f[u][j]+(ll)f[u][t]*f[e[i]][j-t]%P*C[j][t])%P;
}
}
for(int i=0; i<=k && i<=siz[u]; ++i) f[u][i]=f[u][i]*2%P;
f[u][0]=(f[u][0]-1+P)%P;
for(int i=0; i<=k && i<=siz[u]; ++i) (ans[i]+=f[u][i])%=P;
++siz[u];
}
int main() {
read(n), read(k);
C[0][0]=S[0][0]=p[0]=1;
for(int i=1; i<=k; ++i) p[i]=p[i-1]*2%P;
for(int i=1; i<=k; ++i) for(int j=0; j<=i; ++j){
C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;
if(j) S[i][j]=(S[i-1][j-1]+(ll)j*S[i-1][j])%P;
}
for(int i=1, x, y; i<n; ++i) read(x), read(y), add(x, y), add(y, x);
dfs(1);
for(int i=0; i<=k; ++i) Ans=(Ans+(ll)ans[i]*S[k][i])%P;
return printf("%d", Ans), 0;
}
|