RainAir
My OI Blog
RainAir


文章归档

FFT 学习笔记

快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种 $ O(n\ log_2\ n) $ 的时间复杂度内完成离散傅里叶变换 (DFT) 的算法,OI 中通常用来优化多项式乘法。 常见题目类型链接: 给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x) $。求出它们的卷积。 FFT …

   364   2018-09-05 去围观

斜率优化

题目链接 其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。 题目描述 你可以连续的输出一些单词,定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。 其…

   222   2018-09-03 去围观

决策单调性优化

写一些简单的 1D/1D 的决策单调性优化... 这种决策单调性优化的过程:列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分 我们以一些例题为例: [ZROI普转提]Bead 题目链接 注:该题有权限,看不到的就看下一题。 这一题我们推出朴素的状态转移方程: …

   211   2018-09-01 去围观
文章归档