这周学习的知识点比较的多，但是真要是说我学会了多少，好像也没有太多完全弄明白的。这周做的题确实也是不少，不过好多都没有完全的弄明白。数论要是想学好确实是非常的难。这周学的内容有：
矩阵乘法、组合计数、高斯消元、容斥原理、博弈论
。
矩阵快速幂
据我所知矩阵乘法最常见的应用就是对于dp的优化了。当dp的n非常大的时候，我们就可以通过矩阵优化将O(n)的时间复杂度降到O(logn)。我感觉它和普通的快速幂一样，是作为一个工具，优化某个过程。矩阵快速幂其实不难，主要的难点还是在于dp。
组合计数
这块的内容主要是高中的排列组合问题。这一块内容比较固定的知识点就只有排列组合的代码实现和卡特兰数了。
C(a,b)的求法一般来说有四种：
1.递推法：
递推公式为：C(a,b)=C(a-1,b)+C(a-1,b-1);
这个递推公式的原理是杨辉三角（不明白的话可以把杨辉三角画出来看看就明白了）。
递推法的时间复杂度为O(n2)，适合查询次数较多且a和b值范围较小的情况
(1<=b<=a<=2000)
。
2.公式法：
即用C的定义式：C(a,b)=a!/(b!*(a-b)!);
我们可以预处理出所有的n!和1/n!。
//fact[i] 表示i!
//infact[i] 表示1/i!
fact[i]=fact[i-1]*i%mod;
infact[i]=infact[i-1]*qmi(i,mod-2,mod); //qmi(a,k,mod) 快速幂求逆元
//这样就可以求出所有C(a,b)的值了
C[a][b]=fact[a]*infact[b]*infact[a-b]%mod;
公式法的时间复杂度为O(n)，相比于递推法要快很多。
3.lucas定理：
C(a,b)=C(a%mod,b%mod)*C(a/mod,b/mod)(%mod);
int lucas(LL a,LL b)
{
if(a<p&&b<p) return C(a,b);
return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
为lucas定理适用于a和b非常大而mod值较小的情况。用lucas定理一般来说可以非常快的求出C(a,b)的值来。
4.求没用取模运算的组合数
因为没用取模运算，因此结果会非常的大。此时我们就需要用到高精度运算了，除了用高精度运算之外，我们还要减小中间过程中的位数，这就需要我们用分解质因数来完成操作。
C(a,b)=a!/(b!*(a-b)!)
我们可以分解出所有a!、b!、(a-b)!的质因子，然后将所有这些质因子相加减，最后再乘到一块即可得到a!/(b!*(a-b)!)的值。
以上是求组合数的四种方法。除此之外，排列组合专题还有一个非常常用的东西：卡特兰数。
卡特兰数的定义
：给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个（这个问题的结果即为卡特兰数）。
卡特兰数的三种求法：
- 递推法：
c[n]=c[0]c[n-1]+c[1]c[n-2]+……+c[n-1]c[0]=sum(c[k]c[n-1-k]); //[0<=k<=n-1],c[0]=1
-
c[n]=(4n-2)/(n+1)*c[n-1]; //c[0]=1
-
c[n]=C(2n,n)/(n+1)=C(2n,n)-C(2n,n-1);
高斯消元
就是线性代数中n阶线性方程组的求解。用代码实现一下就行了（都学过了，不多说了）。
容斥原理
这其实也算是高中学过的东西了。其基本原理很简单：|s1∪s2|=|s1|+|s2|-|s1∩s2|（但是相关的题目并不是很简单）。这个知识点也不会单独考察，都是与其它知识点相结合来进行考察的（可以与容斥原理结合的知识点很多，比如：排列组合、莫比乌斯函数等等）。
博弈论的相关问题我是几乎没怎么弄明白，都非常的复杂。相关的题目都做的我一蒙一蒙的。。。等我下周抽出些时间来再整理整理把。
下周的话我打算把这周和上周数论做的题目都整理一下（有很多题确实是没怎么弄明白）。写一下严谨的数学推导，再重新的想一想这些题目（下周就不再做新题了）。整理的题目我们会发题解出来的，虽然一周全整理出来的可能性不是很大，但是我尽量多整理一些出来把。下下周的话我会根据情况学一下最大流或者是数据结构（splay等等）的一些内容。
