本文主要是介绍2018.11.30 多项式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意: 求n个点的二分图,将其所有边都黑白染色后不同的图的数量,两个图不同当且仅当x-y 这条边只在一个图中出现或者两张图中颜色不同。
n 1e5
多项式模板题。
首先我们考虑联通二分图的生成函数G
容易知道答案F = e^G.
联通二部图的数量的生成函数 H=e ^ (2G) 所以我们只需要计算出H然后多项式开根就是答案。
H 的 n 次项显然是 sigma i = 1 - n C(n, i) * 3^ (n - i * i)
我们发现这个 3^ (n - i) * i 很难处理,这里用了一个比较巧妙的构造思想。
令 I 为 sigma i >= 1 (1 /3) ^ (C(i, 2)) * (1/i!)
利用 I * I 经过一系列的推式子就可以得到H。
剩下就是一个开根了。 顺便大了一遍多项式板子。
这篇关于2018.11.30 多项式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!