简述
在信息学竞赛中，多项式乘法出现得非常的多，朴素算法的时间复杂度为\(O(n^2)\)，成为了许多毒瘤出题人卡指数的地方。所以，用快速傅立叶变换（FFT, Fast Fourier Transform）来优化多项式乘法是很有必要的。接下来，我会由浅入深地来介绍这两者与其之间的关系。
「Fortuna OJ」Jul 4th – Group A 解题报告
A – 非回文数字
这道题还没写，是一道数位 DP，推荐记忆化搜索。
B – 管道
这道题是一道相当好的题目。
首先对于\(m = n – 1\)的情况，也就是树的形态下，可以考虑自下向上推，也就是从叶子节点开始推起，参考代码中 Toposort 的写法。然后，对于\(m > n\)的情况可以直接输出\(0\)，因为这个方程组并不存在唯一的解：\(m\)个未知数仅提供\(n\)个条件，这样是不成立的。
最后考虑\(m = n\)的情况。这种情况就是基环树了。首先，Toposort 会把支链上的答案全部统计完毕，并且合并到环上的点。最后，我们唯一要多做的事情，就是处理环上的方程组。考虑一个这样的环：
线性基学习笔记
简述
线性基应该算是线性代数范畴内的东西。在 OI 中，线性基被用来解决位运算或者是向量表示的问题。
建议读者学习了高中数学中的向量之后再来阅读本文，相信这样会帮助理解线性基。
P3312:「SDOI2014」数表题解
解法
好题。
我们首先写出这道题的暴力解：
\[ answer = \sum_{i = 1}^n \sum_{j = 1}^m \sigma_1 (gcd(i, j)) [\sigma_1 (gcd(i, j)) \leq limit] \]
复杂度超级大，怎么办？换一种思维来写这个式子，考虑枚举每一个\(gcd(i, j)\)为\(d\)，记起次数为\(g(d)\)，我们可以搞出并化简为：
BZOJ1013:「JSOI2008」球形空间产生器题解
解法
这道题其实就是高斯消元裸题。依照题意可以列出形如以下的方程：
\[ \sum_{i = 1}^n (x_a [i] – x_0 [i])^2 = c \]
其中\(c\)表示球的半径。一共有\(n+1\)个这样的方程，可以考虑上下相减消掉常数，这样就构造出了一个\(n\)个方程的方程组。最终方程组：
\[ \begin{cases} 2\sum_{i = 1}^n x_1[i] x_2[i] = \sum_{i = 1}^n (x_1[i])^2 – (x_2[i])^2 \\ 2\sum_{i = 1}^n x_2[i] x_3[i] = \sum_{i = 1}^n (x_2[i])^2 – (x_3[i])^2 \\ 2\sum_{i = 1}^n x_3[i] x_4[i] = \sum_{i = 1}^n (x_3[i])^2 – (x_4[i])^2 \\ \dots \end{cases} \]
扔到高斯消元里就搞定了。
BZOJ4665:小 w 的喜糖题解
解法
这道题是 DP + 容斥，正好是我不怎么会的类型。设状态\(f[i][j]\)为「考虑了前\(i\)个状态之后有\(j\)个颜色与原来一样的方案数（注意这里颜色不一样不是本质不同的）」。可以推出式子：
\[ dp[i][j] = \sum_{k = 0}^j dp[i – 1][j – k] {cnt[i] \choose k} \frac{cnt[i]!}{(cnt[i] – k)!} \]