FFT 学习笔记
快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种 $ O(n\ log_2\ n) $ 的时间复杂度内完成离散傅里叶变换 (DFT) 的算法，OI 中通常用来优化多项式乘法。常见题目类型链接： 给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x) $。求出它们的卷积。FFT 就可以在 $ n\ log_2\ n $ 的时间复杂度内...
快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种 $ O(n\ log_2\ n) $ 的时间复杂度内完成离散傅里叶变换 (DFT) 的算法，OI 中通常用来优化多项式乘法。常见题目类型链接： 给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x) $。求出它们的卷积。FFT 就可以在 $ n\ log_2\ n $ 的时间复杂度内...
题目链接其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。题目描述你可以连续的输出一些单词，定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。其中 $ N \leq 500000,M \leq 1000 $
写一些简单的 1D/1D 的决策单调性优化...这种决策单调性优化的过程：列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分我们以一些例题为例：
在学习主席树之前一定要先学会线段树主席树定义主要思想：主席树是利用函数式的编程思想使得线段树支持查询历史版本，同时充分的利用不同版本之间的共同版本来减少时间和空间复杂度的数据结构。一棵线段树的节点维护的是当前节点所对应的区间信息，若每次区间不同则处理较为困难。它最基本的运用是区间第 $ k $ 小问题。
定义贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。（摘自百度百科）