今天只写了 2.5 个题，真是太摆了。
讲的是多项式，由周镇东讲解，讲的很详细。
前面是 fft 的一些奇技淫巧，分治 fft 比较板子，n 年前就已经完全明白了。简而言之就是考虑左边对右边的贡献，注意一定要完整计算完之后才能贡献。
接下来是高维 fft，感觉没有什么用，毕竟例题一道没放，感觉其实本质很像子集卷积，先卷一个维度，再在另一个维度卷，只不过 fwt 中是暴力卷 popcount 那一维。
然后是循环卷积，比较观察的一点是其实 dft 等于做了一次循环卷积，因为其实 \(\omega_{n}^i \times \omega_n^j = \omega_n^{(i+j)\mod n}\)，这就是为什么我们 dft 的时候要预留位数。
然后就是任意长度循环卷积，其实没什么用，只是在求多次幂的时候会比直接卷积少一个 \(\log\)，因为直接循环卷积就只用求 \(n+1\) 个点值，每次是不变的，不用像直接卷积一样驱魔。但是有一个专门的算法叫 bluestein（避雷这个算法，写了一下午+一晚上，难写 + 卡精度 + 卡空间 + 长度长）。
具体说，我们考虑每次 dft 到底在干什么，发现是在求 \(f(\omega_n^i)\sum_{j=0}^n \omega_n^{ij}\)，我们考虑把这个 \(ij\) 转化掉，注意到 \(ij = \frac{(i+j)(i+j-1) - i(i-1)-j(j-1)}{2}\)，并且这几项都是可以被 \(2\) 整除的，这很重要，这也是为什么我们不能转化成 \(i^2+j^2-(i-j)^2\) 之类的式子的原因，然后就变成了一个卷积的形式，我们可以直接卷起来。
例题是 P4191，这个题就是直接卷就可以了，讲一些实现上的问题。
这个题基本上使用 fft 才行，因为你的模数是 \(n+1\)，肯定是不能 ntt 的，虽然讨论区里有个不知道怎么写的老哥写的貌似是 ntt。
然后当你打完之后你会发现你 WA 70pts，因为 n = \(5\times 10^5\)，这么大的范围很容易爆精度爆的妈妈都不认识，所以我们考虑怎么去优化精度。我们这里考虑将多项式拆位，将每个系数 \(a_i\) 拆成 \(a_{i,1}\sqrt{mod} + a_{i,2}\)，然后分成两部分分别卷再进行贡献，然后你会直接多一个 2 倍常数，幸好没被卡。
然后你会发现，欸，怎么 80pts mle 了，这个我也不知道怎么解决，因为我就算全开成 int 和 double 也没能解决这个问题，包括洛谷唯一一篇有代码的题解我交了一发也 mle 了，最后贺了讨论区老哥的代码上去，不知道为什么空间奇小，感觉他开小了很多不合理的地方但是他就是过去了，神秘。
这里应该有一个 hdu 4656 的题解，但是写 bluestein 这个幽默东西写弘文了，等着后面填坑。
然后就是生成函数，这部分主要是结合计数方法，基本上把 dp 式子写出来发现可以卷积就可以优化了。
这里应该有几道例子的题解，等着后面填坑。