A – Fibonacci
sb 题，直接矩阵快速幂即可。
多项式求逆
前置技能
FFT、NTT、多项式乘法。
原理推理
现在我们有一个这样的式子：
\[ A(x)B(x) \equiv C(x) \ (mod \ x^n) \]
现在我们已知\(B(x), C(x)\)的信息，而我们计算答案的时候需要用\(A(x)\)进行运算。这个时候，我们需要求出\(B(x)\)的逆元。多项式求逆元，我们一般是用倍增的方式来求解。假如我们有\(B(x)\)在模\(x^{\lceil \frac{x}{2} \rceil}\)意义下的逆元\(D(x)\)：
多项式乘法 & 快速傅立叶变换
简述
在信息学竞赛中，多项式乘法出现得非常的多，朴素算法的时间复杂度为\(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 指针，避免不必要的遍历。