NGC5457

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日

分类