組合數(shù)學(xué)
六合ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書(shū)未來(lái)市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)的ssl證書(shū)銷(xiāo)售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書(shū)合作）期待與您的合作！
排列與組合
抽屜原理（鴿巢原理）
把n+1個(gè)蘋(píng)果放入n個(gè)抽屜里，則至少有一個(gè)抽屜放了兩個(gè)或兩個(gè)以上的蘋(píng)果；
從另一個(gè)角度來(lái)說(shuō)，把n-1個(gè)蘋(píng)果放入n個(gè)抽屜，則至少有一個(gè)抽屜是空的。
如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋(píng)果就可以代表一個(gè)元素。
假如有n+1個(gè)元素放入n個(gè)集合，其中必定有一個(gè)集合里至少有兩個(gè)元素；
把n-1個(gè)元素放入n個(gè)集合，則至少有一個(gè)集合是空的。
通常來(lái)說(shuō)，在問(wèn)題中，較多的一方就是蘋(píng)果，較少的一方就是抽屜。
最差原則
即考慮所有可能的情況中，最不利于某件事情 發(fā)生的情況。
容斥原理
基本計(jì)數(shù)原理
分類(lèi)加法計(jì)數(shù)原理
做一件事，完成它有 \(n\) 類(lèi)方法，第一類(lèi)有 \(m_{1}\) 種，第二類(lèi)有 \(m_{2}\) 種，……，第 \(n\) 類(lèi)有 \(m_{n}\) 種，那么完成這件事共有 $ s=m_{1}+m_{2}+…+m_{n}$ 種方法。
特點(diǎn)
分類(lèi)加法計(jì)數(shù)原理與分類(lèi)有關(guān)，各種方法相互獨(dú)立，用其中任一方法都可以完成這件事。
特點(diǎn)是分類(lèi)獨(dú)立完成，分類(lèi)計(jì)數(shù)。
分步乘法計(jì)數(shù)原理
做一件事，完成它需要 \(n\) 個(gè)先后步驟，做第一步有 \(m_{1}\) 種不同的方法，做第二步有 \(m_{2}\) 種不同的方法，……，做第n步有 \(m_{n}\) 種不同的方法，那么完成這件事共有 \(s=m_{1}×m_{2}×…m_{n}\) 種不同的方法。
特點(diǎn)
分步乘法計(jì)數(shù)原理與分步有關(guān)，各個(gè)步驟相互依存，只有各個(gè)步驟都完成了，這件事才算完成。
特點(diǎn)是分步依次完成，分步計(jì)數(shù)。
區(qū)別
加法原理是“分類(lèi)完成”，乘法原理是“分步完成”。
排列與組合
定義
階乘
\(n!=1×2×…×n\)
\(\left( 0!=1 \right)\)
排列
從n個(gè)不同元素中任取m(m<=n)個(gè)元素，按照一定的順序排成一列，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。
對(duì)于第一個(gè)位置，我們有n種選擇；第二個(gè)位置，有(n-1)種選擇；……；第m個(gè)位置，有(n-m+1)種選擇；所以，
方案數(shù) \(=n(n- 1)…(n-m+1)\)，即
當(dāng) \(m=n\) 時(shí)，有 \(A^{n}_{n}=n!\) ，稱為 \(n\) 的全排列（n個(gè)不同元素全部取出的排列）；
而 \(0
組合
從n個(gè)不同元素中，任意取出m(m<=n)個(gè)元素并成一組，叫做從n個(gè)不同元素中任意取出m個(gè)元素的一個(gè)組合。
我們考慮從n個(gè)物品中選出m個(gè)物品的排列，由于在組合中不考慮順序性，所以每一種組合在排列中重復(fù)出現(xiàn)了 \(m!\) 次，所以只需要將排列數(shù)除以m!，即
區(qū)別
取出的元素與順序有關(guān)的為排列問(wèn)題，與順序無(wú)關(guān)的為組合問(wèn)題。
公式
該公式是二項(xiàng)式定理，可以證明第三個(gè)公式。
Lucas定理
用于求解大組合數(shù)取模的問(wèn)題，其中模數(shù)必須為素?cái)?shù)。
n%p和m%p一定是小于p的數(shù)，可直接求解；
\(C^{m/p}_{n/p}\)可繼續(xù)用lucas定理求解。這也要求p的范圍不能太大，<=\(10^{5}\)左右。
邊界條件：當(dāng)m=0時(shí)返回1，即， \(lucas(x,0,p)=1\)
楊輝三角
(a+b)n展開(kāi)式的二項(xiàng)式系數(shù)：
性質(zhì)
性質(zhì)1
每行兩端都是1，每個(gè)數(shù)都等于它“肩上”的兩個(gè)數(shù)的和。
性質(zhì)2
每一行中，與首末兩端“等距離”的兩個(gè)數(shù)相等。
性質(zhì)3
如果二項(xiàng)式的冪指數(shù)\(n\)是偶數(shù)，則展開(kāi)中間項(xiàng)\(T_{n/2+1}\)的二項(xiàng)式系數(shù)最大；如果\(n\)是奇數(shù)，展開(kāi)的中間兩項(xiàng)\(T_{(n+1)/2}\)和\(T_{(n+1)/2+1}\)的系數(shù)最大。
性質(zhì)4
二項(xiàng)式每行的系數(shù)和等于2n。
組合數(shù)求解
用組合數(shù)遞推公式求解。
復(fù)雜度\(O(n^{2})\)
初始條件：
組合數(shù)學(xué)相關(guān)
錯(cuò)排、圓排列
基礎(chǔ)數(shù)論
取整
x是一個(gè)實(shí)數(shù)，floor(x)為對(duì)x向下取整，ceil(x)為對(duì)x向上取整。
在c++中，整型變量的除法都是整除的。我們一般考慮除 數(shù)為正的情況。若被除數(shù)為正，則向下取整；為負(fù)則向上取整。
總結(jié)，向絕對(duì)值小的方向取整。
下取整符號(hào) $\left \lfloor \right \rfloor $
上取整符號(hào) $\left \lceil \right \rceil $
取模
a對(duì)b取模得到的結(jié)果就是a除以b的余數(shù)，記作a mod b。
\(x≡y(\) % \(p)\) 表示x與y對(duì)p取模的結(jié)果相等，稱為同余。
性質(zhì)
假設(shè)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
最大公約數(shù)（gcd）/最小公倍數(shù)（lcm）
如果a%x=0，我們稱x是a的約數(shù)(或因數(shù))，稱a是x的倍數(shù)。
a與b的最大公約數(shù)，是指一個(gè)最大的整數(shù)x，使得x同時(shí)是a和b的約數(shù)。
我們將a與b的最大公約數(shù)記作gcd(a,b)。
性質(zhì)
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)
歐幾里得算法（輾轉(zhuǎn)相除法）
時(shí)間復(fù)雜度為log級(jí)。
算法公式
證明
質(zhì)數(shù)（素?cái)?shù)）
一個(gè)大于1的自然數(shù)，除了1和它本身外，不能被其他自然數(shù)整除，這樣的數(shù)稱為質(zhì)數(shù)，否則稱為合數(shù)。
逆元
對(duì)于正整數(shù)a，b，如果能找到正整數(shù)x使得 \(ax≡1(\) % \(b)\) ，我們稱x是a在模b意義下的逆元。
在這里，實(shí)際上a與x互為模b意義下的逆元。
由同余方程可知，a在模b意義下存在逆元，當(dāng)且僅當(dāng)gcd(a,b)=1，即a與b互質(zhì)。
在取模的意義下是不能直接作除法的，但利用逆元?jiǎng)t可以。
在模意義下，除以一個(gè)數(shù)，相當(dāng)于乘上這個(gè)數(shù)的逆元；或者說(shuō)乘以一個(gè)數(shù)，等于除以這個(gè)數(shù)的逆元。
概率和數(shù)學(xué)期望
概率
某個(gè)事件A發(fā)生的可能性的大小，稱之為事件A的概率，記作P(A)。
假設(shè)某事的所有可能結(jié)果有n種，事件A涵蓋其中的m 種，那么P(A)=m/n。
如果兩個(gè)事件A和B所涵蓋的結(jié)果沒(méi)有交集（互不相容），那么P(A或B發(fā)生)=P(A)+P(B)。
如果A和B所涵蓋的結(jié)果有交集，那么P(A或B發(fā)生)=P(A)+P(B)-P(A與B同時(shí)發(fā)生)。
記事件B為“事件A不發(fā)生”（事件A的對(duì)立事件，事件B發(fā)生則事件A不會(huì)發(fā)生）那么P(A)+P(B)=1，即P(B)=1-P(A)。
在兩個(gè)互不干擾的事中，事件A在其中一件事中，事件B在另外一件事中（獨(dú)立事件，事件A發(fā)生跟B的發(fā)生沒(méi)有關(guān)系），那么P(A與B同時(shí)發(fā)生)=P(A)×P(B)。
數(shù)學(xué)期望
事件A有多種結(jié)果，記其結(jié)果為x，那么x的期望值表示事 件A的結(jié)果的平均大小，記作E(x)。
E(x)=每種結(jié)果與其概率的乘積的和
記兩個(gè)事件的結(jié)果分別為x、y，那么，E(x+y)=E(x)+E(y)
若兩個(gè)事件互相獨(dú)立，那么，E(xy)=E(x)·E(y)
若c為常數(shù)，那么，E(x+c)=E(x)+c，E(cx)=c·E(x)
并非原創(chuàng)，僅是整理，請(qǐng)見(jiàn)諒
重慶分公司
重慶分公司
