关键词：
本次笔记学习自算法导论
FFT核心:系数表示→(单位复数根)点值表示→(插值)系数表示
关于单位复数根
n次单位复数根\(ω\)为满足\(ω^n=1\)的复数
n次单位复数根恰好有n个,表示为\(ω_k,k=0,1,...n-1\)
由欧拉公式\(e^iθ=cosΘ+isinΘ\),得\(ω_k=e^i2πk/n\)
主n次单位根\(ω_n=e^2πi/n\),其他n次单位复数根都是\(ω_n\)的幂次,表示为\(ω_n^k,k=0,1,...n-1\)
\(ω_n^n=ω_n^0\),\(ω_n^j+k=ω_n^(j+k)mod \ n\)
消去引理:对于整数\(n≥0,k≥0,d>0\),\(ω_dn^dk=ω_n^k\)
推论:对于偶数\(n>0\),\(ω_n^n/2=ω_2=-1\)
折半引理:偶数\(n>0\),\(n\)个\(ω_n^k\)的平方的集合 = \(n/2\)个\(ω_n/2^k\) 的集合
简略证明:\(ω_n^k+n/2=ω_n^k*(-1)\),所以平方相等,\(ω_n^2k=ω_n/2^k\),所以每个n次单位复数根的平方都能获得2个n/2次单位复数根
求和引理:对于整数\(n≥1\)和不被\(n\)整除的\(k≥0\),\(\sum_j=0^n-1(ω_n^k)^j=0\)
假设\(n\)为2的幂
多项式\(A(x)=A^[0](x^2)+xA^[1](x^2)\)
\(A^[0](x)=a_0+a_2x+a_4x^2+...+a_n-2x^n/2-1\)
\(A^[1](x)=a_1+a_3x+a_5x^2+...+a_n-1x^n/2-1\)
\(A(x)\)的点值表示可以通过\(A^[0](x)\)和\(A^[1](x)\)来表示,既\((ω_n^0)^2,(ω_n^1)^2,...(ω_n^n-1)^2\)来表示
由折半引理,上式仅由\(n/2\)个\(n/2\)次单位复数根$所组成,所以不断递归子问题规模都会减半
github热点速览vol.27：程序员的自我救赎——github摸鱼(代码片段)
作者：HelloGitHub-小鱼干摘要：都知道VSCode有各种摸鱼小插件，边听云音乐、边在IDE斗地主，再来一个NBA直播，怎一个美滋滋了得。作为VSCode的同门，GitHub在摸鱼上也不输于这个后辈，除了在命令行斗地主的Ratel，还有让你操作安... 查看详情
fft算法学习笔记
写在前边 1.辣鸡RRRR_wys之前csdn的博客，千年不更。。。还很水。。。于是开了这个Blog。。。妄图拯救一下自己 2.最近接触接触了一些多项式理论。于是翘掉了愉快的高频，通过《算导》稍稍学习了一下 3.算法竞赛中... 查看详情
fft学习笔记（自认为详细）
引入什么是$\\textFFT$？反正我看到$\\textwiki$上是一堆奇怪的东西。快速傅里叶变换（英语：FastFourierTransform,FFT），是快速计算序列的离散傅里叶变换（DFT）或其逆变换的方法。傅里叶分析将信号从原始域（通常是时间或空间）转... 查看详情
学习笔记fft(代码片段)
1、内容由于noble_太懒不想写了非常好的博客：https://www.cnblogs.com/rvalue/p/7351400.htmlhttp://www.cnblogs.com/candy99/p/6641972.htmlhttp://www.gatevin.moe/acm/fft%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/ 查看详情
fcsnoi2018福建省冬摸鱼笔记day1
省冬的第一天。带了本子，笔，一本《算法导论》就去了。惊讶于为什么同学不带本子记笔记。他们说：“都学过了。”，果然这才是巨神吧。第一天：数论，讲师：zzx前几页的课件挺水，瞎记了点笔记。后面直接就讲了两道题... 查看详情
fcsnoi2018福建省冬摸鱼笔记day3
第三天。计算几何，讲师：叶芃(péng)。dalao们日常不记笔记。@ghostfly233说他都知道了，就盼着自适应辛普森积分。我计算几何基础不好……然而还是没怎么讲实现，感觉没听什么东西进去。不过还是记了一些公式。同时@ghostfly233... 查看详情
scipy笔记：fft(代码片段)
数学笔记；离散傅里叶变化DFT_UQI-LIUWJ的博客-CSDN博客 数学笔记：FFT（快速傅里叶变换）_快速傅里叶变换矩阵_UQI-LIUWJ的博客-CSDN博客【个人理解：FFT是DFT的一种优化，DFT需要N个谱域信号来表示N个时域信号&... 查看详情
fcsnoi2018福建省冬摸鱼笔记day2
第二天。同学还是不带本子记笔记。dalao。第二天：图论，讲师：@ExfJoe全程划水，前面都讲水算法【虽然我可能已经忘记了】什么最短路，Tarjan，最小生成树，2SAT，差分约束啥的，我现在肯定写不出来啦。后面题目也还挺好，... 查看详情
笔记篇(理论向)快速傅里叶变换(fft)学习笔记w
现在真是一碰电脑就很颓废啊...于是早晨把电脑锁上然后在旁边啃了一节课多的算导,把FFT的基本原理整明白了..但是我并不觉得自己能讲明白...FastFourierTransformation,快速傅里叶变换,是DFT(DiscreteFourierTransform,离散傅里叶变换)的快速... 查看详情
[2017.12.2]fft学习笔记
墙裂推荐两个博客：http://blog.csdn.net/iamzky/article/details/22712347 画了图，写的很容易懂，配合《算法导论》服用更佳http://blog.xlightgod.com/%e3%80%90uoj34%e3%80%91%e5%a4%9a%e9%a1%b9%e5%bc%8f%e4%b9%98%e6%b3%95/ &nb 查看详情
fcsnoi2018福建省冬摸鱼笔记day4
第四天。动态规划专题，讲师：闫神讲了一些DP优化技巧，然而思想难度好大啊……根本没想到能优化那地步，连DP方程都没有呢。不过有几题我还是想明白了。讲了单调队列，决策单调性，四边形不等式，斜率优化，甚至有DP套... 查看详情
多项式乘法(fft)学习笔记(代码片段)
------------------------------------------本文只探讨多项式乘法(FFT)在信息学中的应用如有错误或不明欢迎指出或提问，在此不胜感激多项式1.系数表示法 一般应用最广泛的表示方式 用A(x)表示一个x-1次多项式，a... 查看详情
pytorch笔记：torch.fft(代码片段)
1FFT进行一个维度的快速傅里叶变换torch.fft.fft(input,n=None,dim=-1,norm=None,*,out=None)1.1主要参数input输入，需要傅里叶变换的tensorn需要变换的tensor的长度，默认是input的长度如果比input长度大，那么补0如果比input... 查看详情
[学习笔记]多项式与快速傅里叶变换(fft)基础
引入可能有不少OIer都知道FFT这个神奇的算法,通过一系列玄学的变化就可以在$O(nlog(n))$的总时间复杂度内计算出两个向量的卷积(或者多项式乘法/高精度乘法),而代码量却非常小.博主一年半前曾经因COGS的一道叫做"神秘的常数$pi$"... 查看详情
一键摸鱼神器火了！专为windows系统打造，老板在身后也可以很淡定
...自凹非寺量子位报道|公众号QbitAI哪个打工人，还没点摸鱼小技巧了？这不最近，有一个摸鱼工具，名叫Loaf，就有点火，还冲上过微博热搜。在你安装好应用，点一下左上角的“摸鱼”按钮后，电脑... 查看详情
一键摸鱼神器火了！专为windows系统打造，老板在身后也可以很淡定
...容不迷路量子位报道|公众号QbitAI哪个打工人，还没点摸鱼小技巧了？这不最近，有一个摸鱼工具，名叫Loaf，就有点火，还冲上过微博热搜。在你安装好应用，点一下左上角的“摸鱼”按钮后，电脑... 查看详情
程序员写代码自动工作，每天上班打游戏年薪57万(代码片段)
...EXTFANShttps://mp.weixin.qq.com/s/Lo3XkM1WobMQjl23PgM0hg都说“上班不摸鱼的员工不是好领导”，现如今，上班摸鱼已经成为了许多打工人的常态，为了能够顺利摸鱼，各行各业的打工人也是绞尽了脑汁。如果要问摸鱼技术哪... 查看详情
华为“杀疯了”：发布“摸鱼”神器10余款新品
...。在笔记本电脑上“刷手机”是一种什么感觉？比如摸鱼时间，坐在工位上的你可以在电脑上一键打开“开心消消乐”，而其他人只能去洗手间、吸烟区角落，是不是想想就挺爽的？这不，就在昨天晚上&#x... 查看详情