OI

OI

洛谷题库 P4770 [NOI2018] 你的名字 题解与思路重现

洛谷题库 P4770 [NOI2018] 你的名字 本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用，以及利用可持久化数据结构查询历史区间极值的方法。 也就是说，大体思路只花费一小时不到，去掉一...

More
  • 2022年7月9日
OI

FFT“三次转两次”优化

众所周知，由于做快速傅里叶变换时，要先将两个多项式 $f(x),g(x)$ 分别DFT，点值相乘后再IDFT，其常数是巨大的。但如果其系数均为实数，我们就可以通过构造多项式的方式，充分利用复数虚部存储...

More
  • 2022年7月3日
  • 1
OI

分治FFT与循环卷积

洛谷题库 P4721【模板】分治FFT 给定数列 $g_{1\cdots n}$，求解满足如下形式的数列 $f$：$f_0=1,f_i=\sum_{j=0}^{i-1}f_jg_{i-j},\fora...

More
  • 2022年7月3日
  • 2
OI

牛顿迭代法求多项式域上函数的零点

牛顿迭代法 牛顿迭代法使用泰勒级数的前若干项求出函数零点的近似解。 令 $x_0$ 为我们选定的一个接近函数 $f(x)$ 零点的横坐标。则我们进行若干次迭代。有 $$ x_{n+1}=x_n-\df...

More
  • 2022年6月24日
OI

随记 – 五月二日 – 初探格雷码

格雷码（Gray code）是一种任意两相邻项有且仅有一位不同的二进制编码。 直观来看，其构造方式如下：假如我们构造出了格雷码$g_{0, 1, \cdots, 2^m-1}$，现在考虑构造$m+1$...

More
  • 2022年5月2日

分类