[Matrix-Tree][插值][容斥][prufer序列][DP]夕张的改造

  • 源自 krydom 大爷的 FJ 省冬令营模拟赛题

Statement

  • 给定一棵 \(n\) 个点的树和一个参数 \(k\)

  • 每次操作可以选出树上的一条边删掉,然后再加一条边,使得操作之后还是一棵树

  • 求 \(k\) 次操作能得到多少种不同的树,对 \(998244353\) 取模

  • \(n\le 50\)(原题数据范围)

  • \(n\le 2000\)(加强版)

  • \(n\le 10^5\)(我不会,可以问 PinkRabbit

Solution 1:Matrix-Tree 矩阵树定理+拉格朗日插值 (std)

  • 树有两种常用的计数工具:Matrix-Tree 定理和 prufer 序列

  • 标解的做法是 Matrix-Tree 矩阵树定理

  • 易得我们要求的就是有多少棵树和原树的不同的边数 \(\le k\)

  • 考虑矩阵树定理的本质:求所有生成树的边权积之和

  • 于是我们考虑一个完全图,把每条边定权,如果这条边在原树上则权值为 \(1\),否则为 \(x\)

  • 这样对这个图求一遍 Matrix-Tree 之后得到的答案是一个多项式,\(x^i\) 表示不同的边数恰好为 \(i\) 的生成树个数

  • 这样有一个问题:高斯消元求行列式的复杂度为 \(O(n^3)\),多项式运算的复杂度为 \(O(n^2)\)(用 FFT 可能在常数上还比不过平方),总复杂度 \(O(n^5)\),不太能过

  • 不过最终答案的多项式次数只有 \(n-1\),我们考虑插值,把每条边的权值改为 \(n\) 个点值,可以取 \(1\) 到 \(n\)

  • 这样高斯消元时,多项式乘法就变成了点乘,可以 \(O(n)\) 计算,复杂度为 \(O(n^4)\),可以通过此题

Solution 2:容斥+prufer 序列+树形 DP

  • 如果你做过「WC2019」数树的话,你会发现这是数树的 \(op=1\) 弱化版

  • 考虑如何计算不同的边数恰好为 \(k\) 的方案数

  • 考虑容斥:

  • \[\sum_{m=0}^{k}(-1)^{k-m}\binom{n-1-m}{k-m}f(m)\]

  • \(f(m)\) 表示选出一个大小为 \(n-1-m\) 的边集并让它们和原树相同的方案数,\(\binom{n-1-m}{k-m}\) 的含义是枚举这个 \(f(m)\) 所在的大小为 \(k\) 的集合是哪个

  • 显然 \(f(m)\) 也可以看成原树删掉 \(m\) 条边分成 \(m\) 个连通块之后再连 \(m\) 条边组成一个新树的方案数

  • 可以使用 prufer 序列或 Matrix-Tree 矩阵树定理推出一个结论:

  • \(n=\sum_{i=1}^ma_i\),\(m\) 个连通块,大小分别为 \(a_{1\dots m}\),再加 \(m-1\) 条边形成树的方案数为:

  • \[n^{m-2}\prod_{i=1}^ma_i\]

  • 显然对于所有把原树划分成 \(m\) 个连通块的方案,\(n^{m-2}\) 是确定的,于是我们只需关注 \(\prod_{i=1}^ma_i\)

  • 于是对这个东西进行树形 DP:\(f[u][i][j]\) 表示 \(u\) 的子树选出了 \(i\) 个连通块,其中根所在的连通块大小为 \(j\),除根所在之外的所有连通块大小积之和

  • 大力转移,还是 \(O(n^4)\)

  • 和数树那题一样,如果利用 \(\prod_{i=1}^ma_i\) 的组合意义(每个连通块里选一个点的方案数)可以设计一个新的状态 \(f[u][i][0/1]\) 表示 \(u\) 的子树选出了 \(i\) 个连通块,第三维表示是否已经选出了一个点,这样的复杂度 \(O(n^2)\)

Solution 3

  • 我不会,可以问 PinkRabbit

Code

  • 咕咕咕
上一篇:prufer序列学习笔记


下一篇:BZOJ 1005. [HNOI2008]明明的烦恼