傅里叶变换(FFT)笔记存档
傅里叶变换(FFT)笔记存档
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132582930
参考博客： https://www.luogu.com.cn/blog/command-block/fft-xue-xi-bi-ji
目录：
-
FFT引入
-
复数相关知识
-
单位根及其相关性质
-
DFT过程（难点）
-
DFT结论（重要）
-
IDFT结论（重要）
-
IDFT结论证明（难点）
FFT引入
复数相关知识
单位根及其相关性质
DFT过程
DFT结论
IDFT结论
IDFT结论证明
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-30
FFT代码上的实现细节
FFT代码上的实现细节 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132584208 ω\omegaω 的计算 ωn1\omega_n^1ωn1 的计算 考虑单位圆， ωn1\omega_n^1ωn1 为： 也就是： 注：op为判断当前为dft还是idft ωni\omega_n^iωni 的计算 当要计算 ωni\omega_n^iωni 时，只需要在 ωni−1\omega_n^{i-1}ωni−1 基础上乘 ωn1\omega_n^1...
2023-08-30
多项式乘法（FFT）
多项式乘法（FFT） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132588646 https://www.luogu.com.cn/problem/P3803 傅里叶变换(FFT)笔记存档 FFT代码上的实现细节 主函数 把长度设为2的整数次幂块 初始进行翻转（二进制翻转） 对A，B先化为点值（DFT） 相乘 IDFT FFT函数 进行初始翻转： 枚举区间长度，并计算单位根 逐个枚举区间（哪...
2023-09-25
生成函数套sperner定理+哈夫曼树思想维护多个多项式乘法：CF1257G
生成函数套sperner定理+哈夫曼树思想维护多个多项式乘法：CF1257G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133270189 首先有spener定理，肯定选 m2\frac m 22m 最优 那怎么计算本质不同的选数方案呢？根据一些生成函数的知识，某个质数出现次数为 ccc ，我们就可以令其为 1+x+x2+⋯+xc1+x+x^2+\dots+x^c1+x+x2+⋯+xc ，然后所有多项式相乘的第 m2\frac m 22m 项即为答案...
2026-06-18
容斥原理+哈夫曼式多项式乘法NTT：ABC462G
容斥原理+哈夫曼式多项式乘法NTT：ABC462G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162099398 https://atcoder.jp/contests/abc462/tasks/abc462_g 首先根据容斥原理，我们相当于求： 我们对颜色进行分类，对于颜色 kkk ，我们假设有 XkX_kXk 个球， YkY_kYk 个盒子。 我们现在枚举它有 DkD_kDk 个球放在相应颜色的盒子里，方案有： 因为颜色间不相互影响，所以这...
2023-12-23
平面几何、多项式、斯特林数听课随笔
平面几何、多项式、斯特林数听课随笔 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135166276 平面几何 知识点： 平面凸包 闵和，闵可夫斯基和 P4557 旋转卡壳 半平面交 最小圆覆盖 P4586 P9544 {v1,v2,..,vn}\{v_1,v_2,..,v_n\}{v1,v2,..,vn} 的凸组合，满足 α1v1+α2v2+…αnvn,αi≥0,∑iαi=1\alpha_1v_1+\alpha_2v_2+\...
2023-09-13
根号分治与多项式的巧妙结合：GYM-104386G
根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于 每种 数的计数问题 考虑对每种数的出现次数进行根号分治 如果出现次数很少，直接平方暴力即可 如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式