简述
在信息学竞赛中，多项式乘法出现得非常的多，朴素算法的时间复杂度为\(O(n^2)\)，成为了许多毒瘤出题人卡指数的地方。所以，用快速傅立叶变换（FFT, Fast Fourier Transform）来优化多项式乘法是很有必要的。接下来，我会由浅入深地来介绍这两者与其之间的关系。
「Fortuna OJ」Jul 8th – Group B 解题报告
今天这几题咋就那么毒瘤呢？
A – String
其实这道题考场上应该能做出来的，是一道很简单的计数问题。在考场上一看到字符串就懵了，不知道为什么我对字符串的字典序有阴影，现在看来就是一道傻逼题。
考虑这样计数：
- 枚举一个\(i\)，考虑前\(i-1\)个字符与\(T\)串相同，然后第\(i\)个字符小于\(T[i]\)，这样可以保证后面怎么放置字母都能满足要求。
- 在枚举了\(i\)的情况下，枚举字符\(ch\)，范围在\([a, T[i])\)，考虑以下两种情况对答案的贡献：
- 如果\(ch = S[i]\)，那么后面需要变动的字符个数为\(k\)个，对答案的贡献：\[ {n – i \choose k} 25^{k} \]
- 如果不等于，那么后面需要变动的字符个数为\(k-1\)个，因为本位占了一个；对答案的贡献：\[ {n – i \choose k – 1} 25^{k – 1} \]
- 贡献之后，如果本位\(T[i] \neq S[i]\)，那么把\(k–\)，代表多固定了一个不同的字符。
「Fortuna OJ」Jul 5th – Group A 解题报告 / 集训队互测 2013
A – 家族
这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。
考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。
网络流
定义
在有向图中，有唯一的源地（入度为 0）和汇点（出度为 0），每一条边都有非负的容量，且整张图都会保证平衡状态。这样的图叫做网络流图。
基本网络流算法
最大流 – Dinic
每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次，再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。
其中值得一提的是，Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针，避免不必要的遍历。
「Fortuna OJ」Jul 6th – Group B 解题报告
A – 调整 Tweak
这道题我在考场上打了一个错解，还骗到了 30 分。
正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。
「Fortuna OJ」Jul 4th – Group A 解题报告
A – 非回文数字
这道题还没写，是一道数位 DP，推荐记忆化搜索。
B – 管道
这道题是一道相当好的题目。
首先对于\(m = n – 1\)的情况，也就是树的形态下，可以考虑自下向上推，也就是从叶子节点开始推起，参考代码中 Toposort 的写法。然后，对于\(m > n\)的情况可以直接输出\(0\)，因为这个方程组并不存在唯一的解：\(m\)个未知数仅提供\(n\)个条件，这样是不成立的。
最后考虑\(m = n\)的情况。这种情况就是基环树了。首先，Toposort 会把支链上的答案全部统计完毕，并且合并到环上的点。最后，我们唯一要多做的事情，就是处理环上的方程组。考虑一个这样的环：