多项式乘法 & 快速傅立叶变换

简述

在信息学竞赛中,多项式乘法出现得非常的多,朴素算法的时间复杂度为\(O(n^2)\),成为了许多毒瘤出题人卡指数的地方。所以,用快速傅立叶变换(FFT, Fast Fourier Transform)来优化多项式乘法是很有必要的。接下来,我会由浅入深地来介绍这两者与其之间的关系。

继续阅读多项式乘法 & 快速傅立叶变换

莫比乌斯反演与杜教筛

简述

省选级别以上的 OI 赛事中的数学题,相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲:

继续阅读莫比乌斯反演与杜教筛