日记 - 伊埃斯的博客站

四哈希还过不去？？？

发现硬做十分难做，考虑容斥。求出钦定有 $x$ 条边没上色的方案数然后容斥。

设 $dp_{u,i}$ 表示 $u$ 所在的联通块大小是 $i$ 的方案数。那么转移有：

\begin{cases} dp_{u,i} \gets dp_{u,i} + dp_{v,j} \times (-f_j) & v \text{ 不和 } u \text{ 合并} \\ dp_{u,i + j} \gets dp_{u,i} \times dp_{v,i} & v \text{ 和 } u \text{ 合并} \end{cases}

记得先把 $dp_u$ 存到一个 $tmp$ 数组里去，不然会重复转移。

考虑有 $n$ 个数如何做，发现就是 $dis$ 的集合等于给定的数集合。于是我们发动哈希之力，一个换根 dp 解决。

考虑有个数不填如何搞。发现它的影响一定属于这个集合： $\{base^i \mid i \in [0,n)\}$ 。用一个 set 存下这个集合，然后每次判断 $hsh_u - tot$ 是否属于它就是了。

然后这题我双哈希没过去，三哈希没过去，四哈希还没过去。

于是写了个十哈希草过去了。

Thanks for reading!

周二 7月 15 2025

276 字 · 2 分钟