加法原理

完成一件事情，有N類方式去實作，第一類方式有 a 1 a_1 a1?種，第二類方法有 a 2 a_2 a2?種，…，第N類方法有 a n a_n an?種，則完成這件事情的總方法數為：
∑ i = 1 N a i \sum_{i=1}^N a_i i=1∑N?ai?
例如：從北京到上海有火車、飛機、輪船 3 種方式，火車、飛機、輪船分別有 a1，a2，a3 個班次，那么從北京到上海有 a1+a2+a3 種方式可以到達，

乘法原理

做一件事，完成它要分成 n 個步驟，第一步有 a 1 a_1 a1? 種不同的方法，第二步有 a 2 a_2 a2? 種不同的方法，…，第 n 步有 a n a_n an? 種不同的方法，那么完成這件事共有 a 1 × a 2 × a 3 × … × a n a_1 ×a_2×a_3×…×a_n a1?×a2?×a3?×…×an? 種不同的方法

例如：從北京乘坐火車到上海，需要轉 3 次車，每次專車分別有 a1，a2，a3 個班次，那么從北京到上海有 a1×a2×a3 種方式可以到達，

排列組合

在排列與組合問題中，經常會出現計數問題，解決計數問題的思路一般有以下三種：

1）只取需要的，將各種符合條件的情形列舉出來，再利用加法原理求和，

2）先取后排，將各步符合條件的排列或組合計算出來，再根據乘法原理求積，

3）先全部取，再減去不要的，利用容斥定理，將各種符合條件的情形列舉出來，再減去不符合條件的，

排列數

從 n n n個不同元素中取出 m ( m < = n ) m(m<=n) m(m<=n)個元素的所有排列的個數，叫做從 n n n個不同元素中取出 m m m個元素的排列數，?符號 A n m A_n^m Anm?表示
A n m = n ! ( n ? m ) ! A_n^m=\frac{n!}{(n-m)!} Anm?=(n?m)!n!?

組合數

從 n n n個不同元素中取出 m m m個元素的所有組合的個數，叫做從 n n n個不同元素中取出 m m m個元素的組合數，?符號 C n m C_n^m Cnm?或 C ( n , m ) C(n,m) C(n,m)來表示
C n m = A n m m ! = n ! m ! ( n ? m ) ! C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!} Cnm?=m!Anm??=m!(n?m)!n!?

組合恒等式

1） C n m = C n n ? m C_n^m=C_n^{n-m} Cnm?=Cnn?m?

2） C n m = C n ? 1 m + C n ? 1 m ? 1 C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1} Cnm?=Cn?1m?+Cn?1m?1? ★

3） C n m = n m C n ? 1 m ? 1 C_n^m=\frac{n}{m}C_{n-1}^{m-1} Cnm?=mn?Cn?1m?1?

4） C n m + 1 = n ? m m + 1 ? C n m C_n^{m+1}=\frac{n-m}{m+1}*C_n^m Cnm+1?=m+1n?m??Cnm?

5） ( a + b ) n = ∑ k = 0 n C n k a n ? k b k (a+b)^n=\sum_{k=0}^nC_n^ka^{n-k}b^{k} (a+b)n=∑k=0n?Cnk?an?kbk（二項式定理）

特殊展開： 2 n = C n 0 + C n 1 + . . . + C n n ? 1 + C n n 2^n=C_n^0+C_n^1+...+C_n^{n-1}+C_n^n 2n=Cn0?+Cn1?+...+Cnn?1?+Cnn?

6） C n m C_n^m Cnm? 為奇數時有 n&m=n

求組合數的方法

遞推求組合數 O ( n m ) O(nm) O(nm)

// c[a][b] 表示從a個蘋果中選b個的方案數
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

乘法逆元求組合數 O ( n ) O(n) O(n)

首先預處理出所有階乘取模的余數fact[N]，以及所有階乘取模的逆元infact[N]
如果取模的數是質數，可以用費馬小定理求逆元
int qmi(int a, int k, int p)    // 快速冪模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 預處理階乘的余數和階乘逆元的余數
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

楊輝三角形打表 O ( n m ) O(nm) O(nm)

1 1 1
11 11 11
121 1 21 121
1331 1 3 3 1 1331
14641 1 4 6 4 1 14641
…
我們不難發現其規律，每個數字等于其左上和上端的值，給定第 i i i行第 j j j列有，
a [ i ] [ j ] = a [ i ? 1 ] [ j ] + a [ i ? 1 ] [ j ? 1 ] a[i][j] =a[i-1][j]+a[i-1][j-1] a[i][j]=a[i?1][j]+a[i?1][j?1]
組合恒等式有： C n m = C n ? 1 m + C n ? 1 m ? 1 C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1} Cnm?=Cn?1m?+Cn?1m?1? ★
那么，楊輝三角形第 i i i行第 j j j列可表示為： c i j c_ i^ j cij?

 	f[0][0]=1;
    for(int i = 1; i < N; i++)
        for(int j = 1; j <= i + 1; j++)
            f[i][j] = f[i - 1][j] + f[i - 1][j - 1];

排列組合的應用

逐分法

需要分步驟完成的事件，我們首先想到的是乘法原理，對待事件逐一分配，

【例題】現在有12位警察，要分到3個路口每個路口4個人有多少種方案

【決議】第一個路口有 C 12 4 C_{12}^4 C124?種選法，因為第一個路口已經用去了4位警察，所以第二個路口就只有 C 8 4 C_8^4 C84?種了，第三個也只有 c 4 4 c_4^4 c44?種了，根據乘法原理就可以得出總共的方案數就是 C 12 4 × C 8 4 × C 4 4 C_{12}^4×C_8^4×C_4^4 C124?×C84?×C44?

捆綁法

要求元素相鄰時，先整體考慮，將相鄰元素視作一個大元素進行排序，然后再考慮大元素內部各元素間順序，

【例題】由數字1、2、3、4、5、6、7組成無重復數字的七位數，求三個偶數必相鄰的七位數的個數，

【決議】因為三個偶數2、4、6必須相鄰，所以先將2、4、6三個數字“捆綁”在一起有 A 3 3 A_3^3 A33?=6種不同的“捆綁”方法;再將捆綁后的元素與1、3、5、7進行全排列，有 A 5 5 A_5^5 A55?=120種方法，根據乘法原理共有6×120=720種不同的排法，所以共有720個符合條件的七位數，

插空法

要求元素不相鄰時，先將其他元素排好，再將所指定的不相鄰的元素插入它們的間隙或兩端位置，從而解決問題，

【例題】由數字1、2、3、4、5、6、7組成無重復數字的七位數，求三個偶數互不相鄰的七位數的個數，

【決議】因為三個偶數2、4、6互不相鄰，所以先將1、3、5、7四個數字排好，有 A 4 4 A_4^4 A44?=24種不同的排法，再將2、4、6分別“插入”到第一步排的四個數字的五個“間隙”(包括兩端的兩個位置)中的三個位置上，有 A 5 3 A_5^3 A53?=60種排法，根據乘法原理共有24×60=1440種不同的排法，所以共有1440個符合條件的七位數，

隔板法

把 n n n個相同的蘋果分給 k k k個人，要求每個人至少分到一個，求方案數，

把 n n n個蘋果排成一排，在其中插入 k ? 1 k?1 k?1塊隔板，表示 k k k個人分到的部分，

插隔板的方法與分蘋果的方案是一一對應的，那么方案數為 C n ? 1 k ? 1 C_{n?1}^{k?1} Cn?1k?1?
那么如果有人可以分到 0 0 0個蘋果呢？

我們給每個人多分一個蘋果，使得每個人至少分配到一個蘋果，在分配完之后再將每個人的蘋果拿走一個，

那么方案數為 C k + n ? 1 k ? 1 C_{k+n?1}^{k-1} Ck+n?1k?1?(先給k個蘋果，讓他們一人一個，再分n個蘋果，)
隔板法與不定方程整數解的問題
求不定方程 x 1 + x 2 + x 3 + x 4 + . . . + x k = n x_1+x_2+x_3+x_4+...+x_k=n x1?+x2?+x3?+x4?+...+xk?=n的解的個數，要求 x i > d i x_i>d_i xi?>di?
設 y i = x i ? d i > 0 y_i=x_i-d_i>0 yi?=xi??di?>0
那么有 y 1 + y 2 + y 3 + . . . + y k = n ? ( d 1 + d 2 + d 3 + . . . + d k ) y_1+y_2+y_3+...+y_k=n-(d_1+d_2+d_3+...+d_k) y1?+y2?+y3?+...+yk?=n?(d1?+d2?+d3?+...+dk?)
答案: C n ? ( d 1 + d 2 + d 3 + . . . + d k ) ? 1 k ? 1 C_{n-(d_1+d_2+d_3+...+d_k)-1}^{k-1} Cn?(d1?+d2?+d3?+...+dk?)?1k?1?

（1） O ? O ? O ? O ? O ? O ? O ? O ? O ? O O-O-O-O-O-O-O-O-O-O O?O?O?O?O?O?O?O?O?O 9個空插3個隔板

答案為： C 9 3 C_9^3 C93?

（2）非負整數意為 x i x_i xi?可以是0，我們可以
( x 1 + 1 ) + ( x 2 + 1 ) + ( x 3 + 1 ) + ( x 4 + 1 ) = 14 (x_1+1)+(x_2+1)+(x_3+1)+(x_4+1)=14 (x1?+1)+(x2?+1)+(x3?+1)+(x4?+1)=14
即為： y 1 + y 2 + y 3 + y 4 = 14 y_1+y_2+y_3+y_4=14 y1?+y2?+y3?+y4?=14,13個空隙中插3個隔板
答案為： C 13 3 C_{13}^3 C133?

（3）根據設 y i = x i ? d i > 0 y_i=x_i-d_i>0 yi?=xi??di?>0
( x 1 + 3 ) + ( x 2 + 2 ) + ( x 3 + 1 ) + ( x 4 ? 1 ) = 15 (x_1+3)+(x_2+2)+(x_3+1)+(x_4-1)=15 (x1?+3)+(x2?+2)+(x3?+1)+(x4??1)=15
即為： y 1 + y 2 + y 3 + y 4 = 15 y_1+y_2+y_3+y_4=15 y1?+y2?+y3?+y4?=15,14個空隙中插3個隔板
答案為： C 14 3 C_{14}^3 C143?