多项式初探

发布于 2018-02-24  3.85k 次阅读


关于多项式这一块,东西实在是太多了,而且现在做的题也不够多,因此只能叫“初探”。

首先,FFT和NTT是最基本的工具,之前学的时候看了很多文章,觉得这些还不错:

有关多项式的算法

从多项式乘法到快速傅里叶变换

模板(其实是一样的,只是把单位复数根换成了原根):

 

FFT的基本应用就不写了,基本上就是推出来卷积的式子或者把序列反过来搞事情。

接下来就写一些有思维含量的应用。

 

BZOJ3771 Triple

求出选1个/2个/3个数的本质不同的方案数。

对于这样的组合计数题,通常是从母函数的角度来解决问题。将原序列转换成一个多项式,对于一个s[i],第s[i]项的系数就是1(因为是算方案),选出1个数的方案数就是多项式的系数和。

对于选2个的方案,另构造一个多项式B(x),对于每个s[i]将第2*s[i]项系数加一,表示同意物品强制选2次的方案(显然不合法)。那么,答案就是A^2/(2!)-B。

对于选3个的方案,构造出C(x),那么答案就是(A^3-3*A*B+2*C)/(3!),其实就是为了刨去不合法方案二进行的手动容斥。

 

BZOJ3992 [SDOI2015]序列统计

同样是利用生成函数来做题。先求出m的原根,那么可以用log[s[i]](其实就是指标)来将乘法转化为加法,那么只需要求生成函数的n次方即可,快速幂可以完成任务。注意,每次做完乘法都要把大于phi(m)的i加到i%phi(m)身上,否则序列的长度就无法保证了。

以上两例主要是生成函数角度的应用。


 

 

BZOJ5093 图的价值

这题太神了,单独写一篇。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974