我有多菜

· · 个人记录

序

去年的8月，我第一次接触了codeforces，这是一个有趣的平台。

现在翻着之前的提交记录，莫名有一些伤感。

那时候被xza带着刷题，一度刷出火花，而如今已经有半年多没有消息往来了。

那个八月，印象最深的那题是一道FWT神仙题，因为早就对FFT,FWT有所耳闻，而且知道那有多难。

记得看到FWT的代码之短，又看到一句话，大概是虽然不知道是怎么构造出来的，但是容易证明它是对的，然后接着一个数学归纳法的证明，我想，我大概也不知道为什么它的，只要知道它是可以用得就行了。于是欢乐地抄完代码，并把原来的式子在一维的情况下暴力展开，发现很有道理，自以为学会了FWT。

去年的寒假，不愿学习文化课，我翻开算法导论，打算窥探神秘的FFT，当时我大抵知道，如果把x代入得到点值，并乘法，最后高斯消元，就可以O(n^2) + O(n)+O(n^3)得到，而FFT就是用来优化左右两边的。当时的我顺着看下去，感觉书上推导得很有道理，便按照书上的做法，写了一份UOJ34的代码。

而后我偶尔了解了或卷积的容斥做法，感觉与卷积也差不多。

渐渐，又听说过了gcd卷积，狄利克雷卷积……

当时我甚至一度以为自己理解了fft的原理，fwt的原理。呵，真是狂妄自大呢。

今天看到一道杜教和妹滋滋的神仙题。

一开始以为自己不会三进制循环卷积。

后来发现自己其实并不会二进制循环卷积。

到最后，甚至发现自己连什么什么卷积都不会……

谁能教教我FFT呀。

What is convolution(in OI)？

我感觉，卷积的定义大概是

设存在两个向量，不妨假设它们的长度相同，设为f(0..n)和g(0..n)，设h = f卷g。

那么对于所有存在的f(0)*g(0),f(0)*g(1)……f(1)*g(0)……这(n+1)^2个元素，每一个都会在某个h(i)中积累。

例如

对于离散卷积，f(i)g(j)->h(i+j)

对于gcd卷积，f(i)g(j) -> g(gcd(i,j))

对于xor卷积，f(i)g(j) -> g(i \text{ xor } j)

对于and卷积，f(i)g(j) -> g(i \text{ and } j)

对于一些数论卷积，f(i)g(j) -> g(i \text{ * } j)