关键词：
任意长度卷积 CZT
就是一波推导
[
eginaligned
b_i &= sum_j=0^n-1 omega^ija_j &= sum_j=0^n-1 omega^fraci^2+j^2-(i-j)^22a_j &= omega^fraci^22 sum_j=0^n-1omega^frac-(i-j)^22 a_j omega^j^2
end aligned
]
后面是一个减法卷积，就可以扩展到2的幂次直接fft就好了。
2次dft计算卷积
考虑有两个长度为(n = 2^k)的序列(a(x), b(x))，我们要计算他们的dft。
构造序列(p_k = a_k + ib_k, ; q_k = a_k - ib_k)，
有结论(dft_q(k) = conj(dft_p((n - k) mod n)))。展开，考虑几何意义？？？
我们可以解出(dft_a, dft_b?)。
再做一遍idft就可以了
拆系数fft
记(M = sqrt mod?)，把(x?)表示成(x = a imes M + b, b < M?)。
((a imes M + b)(c imes M + d) = ac imes M^2 + (ad + bc) imes M + bd)
对每一项分开算，做7次dft就可以了。
套用上述介绍做法4次dft就够了。
实现上注意在idft的时候，直接把一个序列放在real，另一个放在imag，idft回来直接/N后计算贡献就好了。
以及我们可以直接在一个for里面做解出AB，reverse序列的事情。
下面是关键部分的代码。
poly realmain(poly a, poly b)
int n = a.size(), m = b.size();
prepare(n + m - 1);
for (int i = 0; i < n; i++) A[i] = cpx(a[i] & 32767, a[i] >> 15);
for (int i = 0; i < m; i++) B[i] = cpx(b[i] & 32767, b[i] >> 15);
dft(A, fft_n); dft(B, fft_n);
for (int i = 0; i < fft_n; i++)
int j = (fft_n - i) % fft_n;
cpx ax, ay, bx, by;
ax = (A[i] + A[j].conj()) * cpx(0.5, 0);
ay = (A[i] - A[j].conj()) * cpx(0, -0.5);
bx = (B[i] + B[j].conj()) * cpx(0.5, 0);
by = (B[i] - B[j].conj()) * cpx(0, -0.5);
C[j] = ax * bx + ay * by * cpx(0, 1.0);
D[j] = ay * bx + ax * by * cpx(0, 1.0);
dft(C, fft_n); dft(D, fft_n);
poly ans(n + m - 1, 0);
for (int i = 0; i < ans.size(); i++)
lo ax = lo(C[i].x / fft_n + 0.5) % mod;
lo ay = lo(C[i].y / fft_n + 0.5) % mod;
lo bx = lo(D[i].x / fft_n + 0.5) % mod;
lo by = lo(D[i].y / fft_n + 0.5) % mod;
ans[i] = ax + ((by + bx) << 15) + (ay << 30);
ans[i] = (ans[i] % mod + mod) % mod;
return ans;
复习多线程相关知识(代码片段)
多线程操作系统相关冯诺依曼体系结构进程概念进程的组成进程状态时间片并发与并行内核态与用户态线程概念线程优势共享资源进程vs线程线程的创建方式线程的构造函数常见属性常用方法线程终止线程状态图线程安全问题导... 查看详情
bnuoj27935我爱背单词（fft）(代码片段)
...大， 我们还有一种nlogn的算法：FFT仔细观察这个复习单词量的累加方式可以发现，这是一个卷积，可以用FFT加速算法。细节参见代码：#include<cstdio>#include<cstring># 查看详情
26复习(代码片段)
1、基础语法2、数据相关 数据类型（记住每种数据类型到底用来记录什么状态） 每种数据类型相关的内置方法（优先掌握、需要掌握、了解） 文件处理 &... 查看详情
winform复习(代码片段)
WinForm复习0.Form的相关属性Text标题MaximizeBox/MinimizeBox是否使用最大化/最小化按钮。Icon窗体图标，后缀要为.ico的图片。FormBorderStyle窗体边框如果前缀为Fixed表示窗体大小固定，即不能放大缩小边框。StartPosition窗体首次启动... 查看详情
[oc学习笔记]gcd复习(代码片段)
有关GCD的相关内容，我之前也有提到过：[OC学习笔记]浅学GCD线程相关内容、[OC学习笔记]GrandCentralDispatch。GCD线程间的通信在平常的开发过程中，我们一般在主线程里边进行UI刷新，然后通常把一些耗时的操作放在... 查看详情
dsp5509项目之用fft识别钢琴音调(代码片段)
...难点在于，能不能采集到高质量的钢琴音调。先看一下FFT相关程序。FFT并不是一种新的变换，它是离散傅立叶变换（DFT）的一种快速算法。由于我们在计算DFT时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需... 查看详情
算法专栏概述(代码片段)
在复习的时候写了这个专栏，有3个目的：①记录（记录自己得学习进度）②复习（将思想和相关的代码记录下来方便复习）③分享（分享给处于同一阶段的人） 查看详情
java复习--树(代码片段)
Java复习--树树树的概念树的相关性质树的表示形式树的应用二叉树（非常重要☆）二叉树的概念二叉树的基本形态特殊的二叉树满二叉树完全二叉树二叉树的性质二叉树的存储顺序存储链式存储二叉树的遍历前序遍历中... 查看详情
复习多线程相关知识(代码片段)
多线程操作系统相关冯诺依曼体系结构进程概念进程的组成进程状态时间片并发与并行内核态与用户态线程概念线程优势共享资源进程vs线程线程的创建方式线程的构造函数常见属性常用方法线程终止线程状态图线程安全问题导... 查看详情
线程池相关(代码片段)
支持生产阻塞的线程池,使用了阻塞生产者的方式.把队列设为有限队列.队列满了,调用构造时传入的RejectedExecutionHandler去拒绝任务的处理RejectedExecutionHandler中继续往有界队列中put(阻塞)来添加元素.newRejectedExecutionHandler() @Override publ... 查看详情
实验三：sql语句基础（复习）(代码片段)
...束、删除等）操作实验内容1.根据课堂讲授数据字典相关内容，将本人对数据字典所做的操作语句进行列举，对运行过程或结果截图记录。1、select*fromuser_tables;2、select*f 查看详情
数据结构复习第三章队列(代码片段)
（1）掌握队列的相关概念、特点和基本操作（入队、出队、判队空等）。队列：只允许在表的一端进行插入，而在另一端删除元素的线性表。特点：先进先出(FIFO)基本操作： （2）掌握队列的顺序存储和链式存储的实现。图... 查看详情
fft小结(代码片段)
FFT小结！零，说在前面……令人毒瘤的FFT其实FFT是卷积这个庞大学术课题的一个小应用啦.....WC的时候听卷积定理真是上天的体验那么话不多说我们开始FFT的总结.板子我们就不放了!这个是很基础的,网上也有讲解的很详细... 查看详情
java--泛型复习(代码片段)
...编译过程中，正确检验泛型结果后，会将泛型的相关信息擦除，并且在对象进入和离开方法的边界处添加类型检查和类型转换方法。也就是说，泛型信息不回进入到运行时阶段。泛型类classA&l 查看详情
密码学期末复习(代码片段)
...章目录第一章绪论信息安全概述与密码学组成信息安全的相关标准第二章数学基础有限域数论基础第三章对称密码算法对称加密算法模型DES加密算法AES加密算法第四章对称密码的使用方法对称加密算法实现的保密性对称加密算法... 查看详情
数据结构复习第三章栈(代码片段)
（1）掌握栈的相关概念、特点和基本操作（入栈、出栈、判栈空、获取栈元素等）。栈：限制只能在表的一端进行插入和删除的线性表。允许插入和删除的一端,称为栈顶(top)。不允许插入和删除的另一端，称为栈底(bottom)。把一... 查看详情
浅谈fft(快速傅里叶变换)(代码片段)
...理解和想法。FFT的介绍以及入门就不赘述了，网上有许多相关的资料，入门的话推荐这篇博客：FFT（最详细最通俗的入门手册），里面介绍得很详细。为什么要学习FFT呢？因为FFT能将多项式乘法的时间复杂度由朴素的$O(n^2)$降到$... 查看详情
go语言命令行复习笔记(代码片段)
...交源码，在本机测试的时候这些编译文件都是和系统相关的，但是对于源码管理来说没必要。gofmt有过C/C++经验的读者会知道,一些人经常为代码采取K&R风格还是ANSI风格而争论不休 查看详情