組合數學
排列與組合
抽屜原理（鴿巢原理）
把n+1個蘋果放入n個抽屜里，則至少有一個抽屜放了兩個或兩個以上的蘋果；
從另一個角度來說，把n-1個蘋果放入n個抽屜，則至少有一個抽屜是空的，
如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，
假如有n+1個元素放入n個集合，其中必定有一個集合里至少有兩個元素；
把n-1個元素放入n個集合，則至少有一個集合是空的，
通常來說，在問題中，較多的一方就是蘋果，較少的一方就是抽屜，
最差原則
即考慮所有可能的情況中，最不利于某件事情 發生的情況，
容斥原理
基本計數原理
分類加法計數原理
做一件事，完成它有 \(n\) 類方法，第一類有 \(m_{1}\) 種，第二類有 \(m_{2}\) 種，……，第 \(n\) 類有 \(m_{n}\) 種，那么完成這件事共有 $ s=m_{1}+m_{2}+…+m_{n}$ 種方法，
特點
分類加法計數原理與分類有關，各種方法相互獨立，用其中任一方法都可以完成這件事，
特點是分類獨立完成，分類計數，
分步乘法計數原理
做一件事，完成它需要 \(n\) 個先后步驟，做第一步有 \(m_{1}\) 種不同的方法，做第二步有 \(m_{2}\) 種不同的方法，……，做第n步有 \(m_{n}\) 種不同的方法，那么完成這件事共有 \(s=m_{1}×m_{2}×…m_{n}\) 種不同的方法，
特點
分步乘法計數原理與分步有關，各個步驟相互依存，只有各個步驟都完成了，這件事才算完成，
特點是分步依次完成，分步計數，
區別
加法原理是“分類完成”，乘法原理是“分步完成”，
排列與組合
定義
階乘
\(n!=1×2×…×n\)
\(\left( 0!=1 \right)\)
排列
從n個不同元素中任取m(m<=n)個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列，
對于第一個位置，我們有n種選擇；第二個位置，有(n-1)種選擇；……；第m個位置，有(n-m+1)種選擇；所以，
方案數 \(=n(n- 1)…(n-m+1)\)，即
當 \(m=n\) 時，有 \(A^{n}_{n}=n!\) ，稱為 \(n\) 的全排列（n個不同元素全部取出的排列）；
而 \(0<m<n\) 的情況，則稱為選排列，
組合
從n個不同元素中，任意取出m(m<=n)個元素并成一組，叫做從n個不同元素中任意取出m個元素的一個組合，
我們考慮從n個物品中選出m個物品的排列，由于在組合中不考慮順序性，所以每一種組合在排列中重復出現了 \(m!\) 次，所以只需要將排列數除以m!，即
區別
取出的元素與順序有關的為排列問題，與順序無關的為組合問題，
公式
該公式是二項式定理，可以證明第三個公式，
Lucas定理
用于求解大組合數取模的問題，其中模數必須為素數，
n%p和m%p一定是小于p的數，可直接求解；
\(C^{m/p}_{n/p}\)可繼續用lucas定理求解，這也要求p的范圍不能太大，<=\(10^{5}\)左右，
邊界條件：當m=0時回傳1，即， \(lucas(x,0,p)=1\)
楊輝三角
(a+b)n展開式的二項式系數：
性質
性質1
每行兩端都是1，每個數都等于它“肩上”的兩個數的和，
性質2
每一行中，與首末兩端“等距離”的兩個數相等，
性質3
如果二項式的冪指數\(n\)是偶數，則展開中間項\(T_{n/2+1}\)的二項式系數最大；如果\(n\)是奇數，展開的中間兩項\(T_{(n+1)/2}\)和\(T_{(n+1)/2+1}\)的系數最大，
性質4
二項式每行的系數和等于2n，
組合數求解
用組合數遞推公式求解，
復雜度\(O(n^{2})\)
初始條件：
組合數學相關
錯排、圓排列
基礎數論
取整
x是一個實數，floor(x)為對x向下取整，ceil(x)為對x向上取整，
在c++中，整型變數的除法都是整除的，我們一般考慮除 數為正的情況，若被除數為正，則向下取整；為負則向上取整，
總結，向絕對值小的方向取整，
下取整符號 $\left \lfloor \right \rfloor $
上取整符號 $\left \lceil \right \rceil $
取模
a對b取模得到的結果就是a除以b的余數，記作a mod b，
\(x≡y(\) % \(p)\) 表示x與y對p取模的結果相等，稱為同余，
性質
假設x≡y(%p)
x+a≡y+a(%p)
x-a≡y-a(%p)
ax≡ay(%p)
(a+b)%p=(a%p+b%p)%p
(a-b)%p=(a%p–b%p)%p
(a-b)%p=(a-b+p)%p
ab%p=(a%p)(b%p)%p
最大公約數（gcd）/最小公倍數（lcm）
如果a%x=0，我們稱x是a的約數(或因數)，稱a是x的倍數，
a與b的最大公約數，是指一個最大的整數x，使得x同時是a和b的約數，
我們將a與b的最大公約數記作gcd(a,b)，
性質
lcm(a,b)=ab/gcd(a,b)
gcd(a,b,c)=gcd(gcd(a,b),c)
lcm(a,b,c)=lcm(lcm(a,b),c)
歐幾里得演算法（輾轉相除法）
時間復雜度為log級，
演算法公式
證明
質數（素數）
一個大于1的自然數，除了1和它本身外，不能被其他自然數整除，這樣的數稱為質數，否則稱為合數，
逆元
對于正整數a，b，如果能找到正整數x使得 \(ax≡1(\) % \(b)\) ，我們稱x是a在模b意義下的逆元，
在這里，實際上a與x互為模b意義下的逆元，
由同余方程可知，a在模b意義下存在逆元，當且僅當gcd(a,b)=1，即a與b互質，
在取模的意義下是不能直接作除法的，但利用逆元則可以，
在模意義下，除以一個數，相當于乘上這個數的逆元；或者說乘以一個數，等于除以這個數的逆元，
概率和數學期望
概率
某個事件A發生的可能性的大小，稱之為事件A的概率，記作P(A)，
假設某事的所有可能結果有n種，事件A涵蓋其中的m 種，那么P(A)=m/n，
如果兩個事件A和B所涵蓋的結果沒有交集（互不相容），那么P(A或B發生)=P(A)+P(B)，
如果A和B所涵蓋的結果有交集，那么P(A或B發生)=P(A)+P(B)-P(A與B同時發生)，
記事件B為“事件A不發生”（事件A的對立事件，事件B發生則事件A不會發生）那么P(A)+P(B)=1，即P(B)=1-P(A)，
在兩個互不干擾的事中，事件A在其中一件事中，事件B在另外一件事中（獨立事件，事件A發生跟B的發生沒有關系），那么P(A與B同時發生)=P(A)×P(B)，
數學期望
事件A有多種結果，記其結果為x，那么x的期望值表示事 件A的結果的平均大小，記作E(x)，
E(x)=每種結果與其概率的乘積的和
記兩個事件的結果分別為x、y，那么，E(x+y)=E(x)+E(y)
若兩個事件互相獨立，那么，E(xy)=E(x)·E(y)
若c為常數，那么，E(x+c)=E(x)+c，E(cx)=c·E(x)
并非原創，僅是整理，請見諒
Lo問我為什么看星星，我覺得銀河和代碼是同一種東西，這也是一種回答，————Co轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/482107.html
標籤：C++
上一篇：單鏈表的創建
下一篇：SMFL 教程&個人筆記（2）