知识

「OI」莫比乌斯反演

莫比乌斯反演是数论中的重要内容。对于一些函数 $ f ( n ) $,如果很难直接求出它的值,而容易求出其倍数和或约数和 $ g ( n ) $,那么可以通过莫比乌斯反演简化运算,求得 $ f ( n ) $ 的值。

Continue reading…

「OI」快速傅里叶变换 FFT

快速傅里叶变换 $\texttt{FFT}$ 支持在 $\Theta(n\log _ 2n)$ 的时间内计算两个 $n$ 度的多项式的乘法。由于两个整数的乘法也可以被当作多项式乘法,因此这个算法也可以用来加速大整数的乘法计算。

Continue reading…