数学
比较害怕数学题, 因为数学题一般代码比较短, 一旦想到正解往往就能AC, 但是我数学水平很洼, 知道的东西也比较少. 感觉写写暴力拿部分分比较现实. 毕竟不是每个人都能找到正解.
1. 组合数
- 一般用阶乘计算, 需要求逆元. 可以用lucas定理优化时间复杂度.
- 组合类的问题就要考虑组合数
2. 欧拉函数
- 即 < n 和 n 互质的数的个数
- 当 n 为质数的时候 φ(n)=n-1
- 有一个定理在求逆元的时候很有用: a^φ(p)≡1(mod p) 当 p 为质数时a的逆元就是 a^(p-2) mod p.
3. 离散对数(BSGS算法)
- a^n mod p = b 求 n, 即 log(a, b) (mod p)
4. 容斥原理
5. 解线性模方程(组)
6. 高斯消元
- 一种是解线性一次方程组. 一种是Xor方程组. 前者O(n^3), 后者接近O(n^2)
- 有时Gauss Joran算法比高斯消元更方便
- 在处理无解和多解的时候我不太明白
7. 矩阵乘法
- 这是这里面做题最多的算法了
- 比较有用吧, 主要处理一些死板的而n又很大的递推式
- O(n^3), 如果发现是循环矩阵则可以优化到O(n^2)
8. 群论
9. 其他
总结: 往往一个变形拯救世界. 做数学题就是要开脑洞吧, 敢猜想才更可能找到正解. 猜的方向也很重要.
总结-数学
原文：http://blog.csdn.net/qq_21110267/article/details/44874489
