题解：P15649 [省选联考 2026] 找寻者 / recollector

· · 题解

不会退背包，所以炸完了。

首先考虑期望线性性，转化为每条轻边贡献之和。

那么令 f_{u,l} 表示以 u 为根的子树，重链长度为 l 的概率。

记 u 的 k 个儿子分别为 v_1,\dots,v_k

转移是显然的，假设已知各个子树重链长度 l_1,\dots,l_k，那么其中选择一个儿子 v_j，就有转移：

\dfrac{\prod_{i=1}^{k}dp_{v_i,l_i}}{\sum_{i=1}^{k} l_i}l_j\rightarrow dp_{u,l_j+1}

观察一下发现是一个卷积形式，把 dp_{v_i} 去掉某一个卷积起来，然后枚举这个儿子的重链长度。

所以关键问题是怎么处理“去掉一个的卷积”。

一个直接做法是前后缀合并，复杂度 \mathcal{O}(n^3)，使用 NTT 优化至 \mathcal{O}(n^2\log n)。

考虑生成函数，记 Q_i=\sum_{l}dp_{v_i,l}z^l=\sum_{l}q_{i,l}z^l，P=\prod_{i=1}^{k}Q_i=\sum_{l}p_lz^l，所求就是 \dfrac{P}{Q_i}。

考虑多项式除法的组合意义，考虑常系数线性递推。

记 G=\dfrac{P}{Q_i}=\sum_{l}g_lz^l，得 P-Q_i G=0。

再记 Q_i=\sum_{j=1}^{n_i}a_jz^{e_j} 满足 e_1<\dots<e_{n_i} 且 a 都是非 0 的，那么就有

p_m-\sum_{j=1}^{n_i}a_{j}g_{m-e_j}=0 p_m-\sum_{j=2}^{n_i}a_{j}g_{m-e_j}=a_1 g_{m-e_1} a_1g_m=p_{m+e_1}-\sum_{j=2}^{n_i}a_{j}g_{m+e_1-e_j} g_m=\dfrac{p_{m+e_1}-\sum_{j=2}^{n_i}a_{j}g_{m+e_1-e_j}}{a_1}

直接递推就可以了。

复杂度因为每个点只会与子树外的点处理至多常数次，因此复杂度是 \mathcal{O}(n^2)。

总结：省选不考多项式。

代码先不放了。