加载中...

FFT代码上的实现细节

发表于2023-08-30|OI（高中）2023-2024赛季

|总字数:229|阅读时长:1分钟|浏览量:

FFT代码上的实现细节

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132584208

$\omega$ 的计算

$\omega_n^1$ 的计算

考虑单位圆， $\omega_n^1$ 为：
在这里插入图片描述

也就是：
在这里插入图片描述

注：op为判断当前为dft还是idft

$\omega_n^i$ 的计算

当要计算 $\omega_n^i$ 时，只需要在 $\omega_n^{i-1}$ 基础上乘 $\omega_n^1$ 即可

初始时实现奇偶翻转

转化为二进制反正

在程序开始，可以先进行好翻转。

初始： 0 1 2 3 4 5 6 7
最终： 0 4 2 6 1 5 3 7

发现其实是对二进制进行翻转，考虑其最后一位的翻转过程：

在这里插入图片描述

先对前面进行翻转，再补上第一位：
在这里插入图片描述

翻转对称性

可以发现，翻转过程具有对称性，所以可以直接暴力翻转：
在这里插入图片描述

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/8556fcd8

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

相关推荐

多项式乘法（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函数进行初始翻转：枚举区间长度，并计算单位根逐个枚举区间（哪...

傅里叶变换(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引入复数相关知识单位根及其相关性质 DF...

NTT总结本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132591415 https://www.luogu.com.cn/problem/P3803 公式： ωn1≡gp−1n(modp)\large\omega_n^1\equiv g^{\frac {p-1}n}\pmod p ωn1≡gnp−1(modp) 然后所有单位根运算都可以转成原根了！（前提 ppp 为质数） ppp 常为 998244353，它的原根 ggg 为 3 实现细节： ...

环上计数+计数转概率：ABC318EX

环上计数+计数转概率：ABC318EX 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650494 https://atcoder.jp/contests/abc318/tasks/abc318_h 先转为概率， fif_ifi 表示 iii 个点两人都AC的概率， gig_igi 表示恰好一个人AC的概率。两个人都AC，只能为全部自环， fi=1i!f_i=\frac 1 {i!} fi=i!1 现在求 gng_ngn 。然后有个定理， ...

生成函数套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 项即为答案...

根号分治与多项式的巧妙结合：GYM-104386G

根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于每种数的计数问题考虑对每种数的出现次数进行根号分治如果出现次数很少，直接平方暴力即可如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式

数据加载中