這周學習的知識點比較的多，但是真要是說我學會了多少，好像也沒有太多完全弄明白的。這周做的題确實也是不少，不過好多都沒有完全的弄明白。數論要是想學好确實是非常的難。這周學的内容有：
矩陣乘法、組合計數、高斯消元、容斥原理、博弈論
。
矩陣快速幂
據我所知矩陣乘法最常見的應用就是對于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等等）的一些内容。
