WC2019

好题啊！

数树

\(\text{opt = 0, 6 pts.}\)

显然答案为 \(y^{n-|E_1∩E_2|}\) 。

\(\text{opt = 1, 47 pts.}\)

\[\sum_{E_2}y^{n-|E_1∩E_2|}
\]

考虑该容斥式：\(f(S)=\sum\limits_{T\subset S}\sum\limits_{P\subset T}(-1)^{|T|-|P|}f(P)\) ，则：

\[\sum_{E_2}\sum_{T\subset E_1∩E_2}\sum_{P\subset T}(-1)^{|T|-|P|}y^{n-|P|}
\]

令 \(g(T)\) 表示包含 \(T\) 的 \(E_2\) 个数。

\[\sum_{T\subset E_1}g(T)\sum_{P\subset T}(-1)^{|T|-|P|}y^{n-|P|}
\]

\[\sum_{T\subset E_1}g(T)y^{n-|T|}\sum_{P\subset T}(-y)^{|T|-|P|}
\]

\[\sum_{T\subset E_1}g(T)y^{n-|T|}\sum_{k=0}^{|T|}\binom{|T|}{k}1^k(-y)^{|T|-k}
\]

\[\sum_{T\subset E_1}g(T)y^{n-|T|}(1-y)^{|T|}
\]

考虑一个定理：给定 \(n\) 个点的森林，有 \(k\) 个连通分量，第 \(i\) 个连通分量的大小为 \(a_i\) ，则由 \(\text{prufer}\) 序列得：生成树的个数为 \(n^{k-2}\prod\limits_{i=1}^{k}a_i\) 。

代回原式，记 \(k=n-|T|\) ，表示连通分量个数：

\[\sum_{T\subset E_1}y^k(1-y)^{n-k}n^{k-2}\prod_{i=1}^{k}a_i
\]

\[\frac{(1-y)^n}{n^2}\sum_{T\subset E_1}\prod_{i=1}^{k}\frac{ny}{1-y}a_i
\]

发现一个大小为 \(a_i\) 的连通分量对答案的贡献为 \(Ka_i\) ，其中 \(K=\frac{ny}{1-y}\) 为一个常量。

考虑贡献的组合意义，大小为 \(a_i\) 的连通分量贡献相当于在这个连通分量重选取一个点，产生 \(K\) 的乘积贡献。

据此，可进行 \(dp\) ：\(\mathrm{f[u][0/1]}\) 表示在 \(u\) 的子树中，当前连通分量是否已经做出贡献的答案。这里为了方便转移，当前连通分量若已做出贡献，就计入答案。

int f[N][2], K;

void dfs(int u, int fa) {

  f[u][0] = 1, f[u][1] = K;

  for (auto v: adj[u]) {

    if (v == fa) continue;

    dfs(v, u);

    f[u][1] = (1ll * f[u][0] * f[v][1] + 1ll * f[u][1] * f[v][0] + 1ll * f[u][1] * f[v][1]) % mod;

    f[u][0] = (1ll * f[u][0] * f[v][0] + 1ll * f[u][0] * f[v][1]) % mod;

  }

}

\(\text{opt = 2, 47 pts.}\)

\[\sum_{E_1}\sum_{E_2}y^{n-|E_1∩E_2|}
\]

\[\sum_{E_1}\sum_{E_2}\sum_{T\subset E_1∩E_2}\sum_{P\subset T}(-1)^{|T|-|P|}y^{n-|P|}
\]

这一段类似 \(\text{opt = 2}\) ，直接快进：

\[\sum_{T}g^2(T)y^{n-|T|}(1-y)^{|T|}
\]

\[\sum_{T}y^k(1-y)^{n-k}n^{2(k-2)}\prod_{i=1
}^{k}a_i^2\]

\[\frac{(1-y)^n}{n^4}\sum_{T}\prod_{i=1}^{k}\frac{n^2y}{1-y}a_i^2
\]

换个角度考虑，每个连通分量是无序的，相当于有 \(n\) 个有标号小球扔进 \(k\) 个无标号盒子，盒子不为空。

对于一个装有 \(a\) 个球的盒子，一个生成树对其贡献为 \(\frac{n^2y}{1-y}a^2\) 作为乘积，有 \(a^{a-2}\) 个生成树，因此总乘积贡献为 \(\frac{n^2y}{1-y}a^a\) 。

显然，总方案的 \(EGF\) 等于 \(exp\) 单个盒子的 \(EGF\) ，即：

\[F=\sum\limits_{i=1}^{\infty}\frac{n^2y}{1-y}i^i\frac{x^i}{i!}
\]

\[G=exp(F)
\]

答案即为：

\[\frac{(1-y)^n}{n^4}n![x^n]G
\]

套多项式 \(exp\) 即可。

时间复杂度 \(O(nlogn)\) 。

巴特西

WC2019

数树

最新文章

热门文章