嘛，由于各种原因，job 不少提高组算法都还有所欠缺（2-sat,点分治,平衡树,BSGS,CRT,AC 自动机,主席树,cdq分治,整体二分），还有不少已经学习过的省选算法有所遗忘/当时摆大烂没学（莫比乌斯反演，多项式科技）
所以开篇文章来声讨总结一下哪些算法俺不行的，坚持日更。
排序仅按照复习/学习的顺序排序。
标题按以下标准来严格划分 :
-
二级置顶 ： 来存大标题。例如：数学，杂项。
-
三级置顶 ： 在大标题下存在的小标题。例如：斯特林数学习总结。
-
五级置顶 ： 用以分割一个模块的段落。例如：理论部分，具体例题。
-
高亮 ： 及重要的关键要点，必需进行记忆。
-
加粗 ： 用来提示出重点内容。
1.数学：
目前可能包含的部分：数论，组合数学，多项式科技。
① 多项式科技：
用途：
- 当算术式为两个 \(\sum\) 时，注意是否可以化为 \(i\),\(j\) 两个满足卷积形式的部分，可将时间优化至 \(O(nlogn)\)。
- 半在线卷积。求类似 \(f(n) = \sum_i^{n-1}f(i)*g*(n - i)\) 算式（多项式 exp/分治 FFT）。
- 求类似斯特林数/生成函数。
- \(O(lenlog(len))\) 高精度乘法
基础知识：
FFT/NTT:
可行性来自于 \(O(nlogn)\) 的 DFT/IDFT （本质上是单位根反演）。
需要单位根满足:
- \(w_n^k = (w_n^1)^k\)。
- \(w_n^k,k \in[0,n -1]\) 互不相同。
- \(w_n^k = w_n^{k\%n}\)。
- \(w_{2n}^{2k} = w_n^k\) 。
于是就可以将单位根带入得到属于原多项式的点值表达式 \(g(n)\) ，根据单位根的性质得到单位根反演，点值相乘之后直接再将系数求出来。
单位根反演：(证明代入后分类讨论)
\[g(w_n^k) = \sum_{i=0}^nf(i)*(w_n^k)^i\\
k*f(k) = \sum_{i = 0}^n g(i)*(w_n^{-k})^i
\]
于是原根也要满足类似的性质，在模 \(998244353\) 基础上，取 \(g^{(mod - 1)/n}\) 最为合适，因为 \(998244352 = 2^{23}*7*17\) 所以 NTT 离了这个模数就死了。