Picks's Blog

Square Root of Polynomial

| Comments

引入

省选结束后就很低沉……于是来出了场CF,搞了搞多项式开方。
相当有意思的问题呢。

问题概述

给出多项式 . 求 .

多项式开方

我们类比于多项式求逆。不妨假设:

显然,. 注意这里的开方可以开出负数。
考虑如何从 推到 .

注意到实际上 的末 位与 一致。故可以同时维护
与多项式求逆的复杂度分析一致,此时我们的复杂度依然是

应用

CodeForces Round 250 E

题意

询问每个点权值在 中,总权值和为 的二叉树个数。
请给出每个 对应的答案。
.

题解

可以很显然地得到递推式:

我们写成母函数形式,令 集合中的数作为指数的和。 的母函数。
我们便可以得到:

最后的1是为了 .
我们解开方程。

其中那个取减号是因为必须取减号……
我们就可以用多项式开方算法将它解决了。
复杂度:.

Comments

comments powered by Disqus