首页 > 其他分享 >快速傅里叶变换

快速傅里叶变换

时间:2024-03-09 22:33:59浏览次数:24  
标签:F1 frac 变换 comp sum FFT 傅里叶 lim 快速

FFT

问题:

设 \(A(x)=\sum_{i=0}^n a_ix^i\),\(B(x)=\sum_{i=0}^m b_ix^i\)。求 \(A(x)\) 和 \(B(x)\) 的卷积。

有一个结论:坐标系中 \(n\) 个点确定一个 \(n-1\) 次函数。

可以这样理解:\(n-1\) 次函数有 \(n\) 个系数,而 \(n\) 个点相当于 \(n\) 个方程。

于是我们可以换一种思路求卷积:将 \(n+m+1\) 个不同的 \(x\) 代入多项式,那么其卷积的结果的函数 \(C(x)\) 必然经过 (\(x_i,A(x_i)B(x_i)\)),于是再通过插值就可以得到卷积结果了。

但是,这样子复杂度仍然不变,那该怎么办呢?

于是我们考虑用复数解决问题,在一个单位圆上,圆上的点表示 \(z=\cos\theta+i\sin\theta\)(\(0\le \theta< 2\pi\))。然后我们把圆分成 \(n\) 等份,便有了单位根:\(w_n^k=\cos{\frac{2\pi k}{n}}+i\sin{\frac{2\pi k}{n}}\),它有很好的性质:

1.\(w_n^a\times w_n^b=w_n^{a+b}\),其实就是积化和差直接推式子就可以证了,并且也可以通过这个简单推出 \((w_n^a)^b=w_n^{ab}\)。不过这个式子其实是最最最重要的,也是唯一用到虚数的性质。

2.\(w_n^{k+\frac{n}{2}}=-w_n^k\),学过三角函数就会发现很显然。

3.\(w_n^{2k}=w_{\frac{n}{2}}^k\),显然。

4.\(w_n^k=w^{k+n}\),显然。

然后,考虑如何快速计算多项式的值,通过思考可以得到:

\[\begin{align} A(x)&=a_0+a_1x^1+\cdots+a_{n-1}x^{n-1}+a_nx^n \\ &=(a_0+a_2x^2+\cdots+a_{n-2}x^{n-2})+(a_1+a_3x^2+\cdots+a_{n-1}x^{n-2})x\\ &=A_1(x^2)+A_2(x^2)x\end{align} \]

注意:\(A_1(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{\frac{n}{2}-1}\),\(A_2\) 同理可推,然后在 FFT 中我们规定 \(n=2^{i\in \mathbb {Z}}\),并且我们在运算中是不会管第 \(n\) 项的,故 \(n\) 必须大于多项式的次数。

但是这并不能优化我们的复杂度,于是我认为 FFT 一个很厉害的地方来了,我们将单位根 \(w_n^0,w_n^1,\cdots,w_n^{n-1}\) 分带入多项式并求值,那么:

\(A(w_n^k)=A_1(w_{\frac{n}{2}}^k)+w_n^kA_2(w_{\frac{n}{2}}^k)\) (\(0\le k < \frac{n}{2}\))

\(A(w_n^k)=A_1(w_{\frac{n}{2}}^k)-w_n^kA_2(w_{\frac{n}{2}}^k)\) (\(\frac{n}{2}\le k <n\))

这样,我们就有了较大的突破,因为这样子,我们要求的东西就是可转移的了,它就相当于一个 \(f(n)=f_1(n)+k\times f_2(n)\),于是,要求它每一项的值就可以通过递归实现了,为了更好的理解这里给出代码:

void FFT (int lim, comp F[])
{
	if (lim == 1) return ;
	comp F1[lim >> 1], F2[lim >> 1];
	rep (i, 0, (lim >> 1) - 1) F1[i] = F[i << 1], F2[i] = F[i << 1 | 1];
	FFT (lim >> 1, F1), FFT (lim >> 1, F2);
	comp w = (comp) {1, 0};
	comp wk = (comp) {cos (2.0 * PI / lim), sin (2.0 * PI / lim)};
	for (int i = 0; i < (lim >> 1); ++ i, w = w * wk)
	{
		F[i] = F1[i] + F2[i] * w;
		F[i + (lim >> 1)] = F1[i] - F2[i] * w;
	}
}

我认为仔细看是可以看懂的,首先我们把系数带进自己的左右节点的数组,然后我们发现每一层完成以后自己的数组变成了每一个 \(F(w_n^k)\) 的答案,然后再转移即可。

于是每个需要的 (\(x_i,A(x_i)B(x_i)\)) 便求出来了,然后我们需要考虑如何通过已有坐标推出多项式系数了。

我们设 \(y_i=A(x_i)B(x_i)\),\(C(x)=\sum_{i=0}^{n-1} y_ix^i\),然后我们分别将 \(w_n^0,w_n^{-1},\cdots,w_n^{1-n}\) 带入进这个多项式,设其结果为 \(z_0,\cdots,z_{1-n}\),我们开始求 \(z\):

\[\begin{align} z_k&=\sum_{i=0}^{n-1}y_i(w_n^{-k})^i\notag\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} a_j(w_n^i)^j(w_n^{-k})^i\notag\\ &= \sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1} (w_n^{j-k})^i\notag\end{align} \]

此时,当 \(j=k\) 时,内部求和的值显然为 \(n\),而当 \(j\neq k\) 时,我们相当于是在求一个等比数列求和,内部求和的值便是 \(\large\frac{(w_n^{j-k})^n-1}{w_n^{j-k}-1}\),其中可以发现 \((w_n^{j-k})^n\) 就是 \(w_n^0=1\),于是内部求和的总和就是零,那么可以得出 \(z_k=na_k\) 即 \(a_k=\frac{z_k}{n}\)。于是我们求出 \(w_n^{-k}\) 就可以求出 \(z_k\) 了,现在考虑怎么求:

设 \(w_n^k=\cos\theta+isin\theta\), 而 \(w_n^{-k}=w^{n-k}\),所以 \(w_n^{-k}=\cos\theta-i\sin\theta\),这个东西也可以通过 FFT 求,于是我们就学会了 FFT 了!接下来上的代码:

void FFT (int lim, comp F[], int op)
{
	if (lim == 1) return ;
	comp F1[lim >> 1], F2[lim >> 1];
	rep (i, 0, (lim >> 1) - 1) F1[i] = F[i << 1], F2[i] = F[i << 1 | 1];
	FFT (lim >> 1, F1, op), FFT (lim >> 1, F2, op);
	comp w = (comp) {1, 0};
	comp wk = (comp) {cos (2.0 * PI / lim), sin (2.0 * PI / lim) * op};
	for (int i = 0; i < (lim >> 1); ++ i, w = w * wk)
	{
		F[i] = F1[i] + F2[i] * w;
		F[i + (lim >> 1)] = F1[i] - F2[i] * w;
	}
}
signed main ()
{
	// freopen ("1.in", "r", stdin);
	// freopen ("1.out", "w", stdout);
	n = rd (), m = rd ();
	int l = 0;
	for (lim = 1; lim <= n + m; lim <<= 1, ++ l) ;
	rep (i, 1, lim) R[i] = (R[i >> 1] >> 1) | (i & 1) << (l - 1);
	rep (i, 0, n) A[i].x = rd ();
	rep (i, 0, m) B[i].x = rd ();
	FFT (lim, A, 1), FFT (lim, B, 1);
	rep (i, 0, lim) A[i] = A[i] * B[i];
	FFT (lim, A, -1);
	rep (i, 0, n + m) printf ("%lld ", (int) (A[i].x / lim + 0.5));
}

这里的 \(op\) 就是表示带进去的是 \(w_n^k\) 还是 \(w_n^{-k}\),然后还有要注意的就是 \(lim\) 其实就是重置成 \(2\) 的次幂的新的 \(n\),显然对于答案不会产生任何影响,并且复杂度跟线段树一样,\(O(n\log n)\)。

这个写法效率很慢,有一个叫蝴蝶变换的更优秀的规律可以优化它,这里不多赘述。

标签:F1,frac,变换,comp,sum,FFT,傅里叶,lim,快速
From: https://www.cnblogs.com/lalaouyehome/p/18063511

相关文章

  • 短多项式快速幂
    求\((x^1+x^2+...+x^k)^n\)的各项系数,要求复杂度\(\Theta(nk)\)。前置知识复合函数\(f[g(x)]\)的求导:\(f[g(x)]'=f'[g(x)]g'(x)\)“左乘右导,右乘左导”:\([f(x)g(x)]'=f(x)g(x)'+f(x)'g(x)\)做法设\(F(x)=x^1+x^2+...x^k\),那么要求的就是\(F(x)^k......
  • Hanoi问题及其相关快速算法
    Hanoi问题抽象hanoi(n,x,y,z)step1:hanoi(n-1,x,z,y)step2:move(x,z)step3:hanoi(n-1,y,x,z)递归部分实现代码voidhanoi(intn,charx,chary,charz){​ if(n==1){ // 递归出口​ move(x,z);​ }​ else{​ hanoi(n-1,x,z,y);​ move(x,z);​ hanoi(n......
  • 中考英语首字母快速突破001-2021上海宝山英语二模
    PDF格式公众号回复关键字:ZKSZM001原文Whatislaughter?Laughterisnaturalforpeople.Westarttolaughataboutfourmonthsofage.Westarttolaughevenbeforewestarttospeak!Laughterissocial.Itconnectsuswithotherpeople.Welaughmorewhenw......
  • 快速排序
    快速排序-V1一、代码实现1.大致思路假如有一个数,这个数组自然有序假如有2个数,我们选第一个数为标准,比它小的数排它前面,比它大排后面,那么这两个数将有序。假如有3个数,我们选第一个数为标准,比它小的数排它前面,比它大排后面。假如有4个数,我们选第一个数为标准,比它小的数排它前......
  • 白菜GPT | 快速上手
    白菜GPT旨在提供稳定高效且免费的OpenAIAPI转发服务,帮助国内GPT应用学习相关爱好者及从业者,提供便捷、低成本、长期稳定的GPT中转服务,免费提供中转API_KEY,从而降低各位学习成本,提高OpenAI学习应用效率,更多学习文档,请参阅官方教程本教程面向第一次接触白菜GPT的用户,仅需四步,即可......
  • [Redis] 01-Redis快速入门
    一、Redis简介Redis属于键值对(key-value)数据库Redis中所有的数据都是以key-value的形式存储在内存中的所以读写Redis非常的快,在高并发的场景下,性能非常的好二、Redis服务端(redis-server)的安装省略。建议使用docker安装。Docker安装redis(保姆级教程&图文并茂)-腾讯......
  • FMS设备监察系统无线传输模块及网关快速应用教程
    设备监察系统又叫做FMS(Facilities  Monitoring  System),该FMS系统由 GUI(配置上位机)、FMS网关和lora无线模块节点三部分组成。亿佰特上市的E53-470FMS22S、E53-DTU(470FMS22)产品是基于LoRa扩频技术开发的设备监察系统无线传输模块及网关,其强大的抗干扰能力,让无线通信在工业现......
  • 快速制定、分解、落地OKR的框架,建议你认真看!
    制定OKR(ObjectivesandKeyResults,目标与关键成果)并没有一套固定的公式,因为每个组织、团队或项目的具体情况和目标都是独特的。然而,有一些通用的步骤和考虑因素可以帮助你制定有效的OKR。以下是一个指导性的框架:一、明确组织或团队的战略目标确定长期和短期目标:明确组织或团......
  • 在Docker中,怎么快速查看本地的镜像和容器?
    在Docker中,查看本地的镜像和容器分别可以通过以下两条命令来快速实现:1.查看本地镜像要查看本地计算机上存储的所有Docker镜像,可以使用dockerimages命令。这个命令会列出所有可用的镜像,包括镜像的存储库名称、标签、镜像ID、创建时间和所占用的空间。dockerimages输出示例:......
  • 瀚高V9的快速安装部署与注意事项
    瀚高V9的快速安装部署与注意事项介质使用上传文件mkdir-p/highgo/opt/highgouseraddhighogochownhighgo/opt/highgo/highgo-Rchmod700/highgo-Rsu-highgo进行执行./bin安装选择路径/opt/highgo输入密码Testxxxxxxxx?!兼容性选择postgresql定......