Category Archives

15 Articles

OI/数学

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

Posted by kal0rona on
多项式乘法 & 快速傅立叶变换

From WallpaperHub.

简述

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

OI/数学

线性基学习笔记

Posted by kal0rona on
线性基学习笔记

简述

线性基应该算是线性代数范畴内的东西。在 OI 中,线性基被用来解决位运算或者是向量表示的问题。

建议读者学习了高中数学中的向量之后再来阅读本文,相信这样会帮助理解线性基。