組合數學基礎 - 學習筆記

1. 加法 / 乘法原理

加法原理

指若有 $n$ 類選擇完成工程，每類選擇有 $a_i$ 個方法，總完成方法數為 $a_1+a_2+ \cdots +a_n$

乘法原理

指若有 $n$ 個步驟完成工程，每個步驟有 $a_i$ 種方法，總完成方法數為 $a_1 \times a_2 \times \cdots \times a_n$

P3197

正面不好想，從反面入手；每個房間的犯人有 $m$ 種選擇，由乘法原理，總共有 $m^n$ 種情況；若每相鄰兩個房間犯人的信仰均不同，從前往后考慮，第一個房間有 $m$ 種選擇，后面每個房間都需要與前一個房間不同，有 $m-1$ 種選擇，因此共有 $m \times (m-1)^{n-1}$ 種情況

答案即為 $m^n-m \times (m-1)^{n-1}$，快速冪即可，實現時注意取?？赡軙霈F負數

2. 排列組合

排列數

指從 $n$ 個元素中選 $m (m \le n)$ 個，按照一定順序 排列的方法數，用符號 $A^{m}_{n}$ 表示

從 $n$ 個元素中選 $m$ 個按順序排列，第 $1$ 個位置有 $n$ 種選擇，第 $2$ 個位置有 $n-1$ 種選擇 (不能選擇第 $1$ 個位置上選過的)，……，第 $m$ 個位置上有 $n-m+1$ 個選擇；因此，$A^{m}_{n} = n \times (n-1) \times \cdots \times (n-m+1)$

在原式上下同乘 $(n-m)!$ (! 表示階乘)，就得到了 $A^{m}_n$ 的計算公式的另一表達形式

\[A^{m}_{n} = n \times (n-1) \times (n-2) \times \cdots \times (n-m+1) = \frac{n!}{(n-m)!} \]

組合數

組合數與排列數略有不同，仍然是從 $n$ 個元素中選 $m(m \le n)$ 個，區別在于它 不考慮順序；組合數用符號 $C^{m}_{n}$ 或 $\dbinom{n}{m}$ 表示

設選出 $m$ 個元素，其不同順序的排列 (就是 全排列 個數) 顯然為 $m!$；因此重復的量為 $m!$，組合數的計算公式即為

\[C^{m}_{n} = \frac{A^{m}_{n}}{m!} = \frac{n!}{m!(n-m)!} \]

特別的，我們規定當 $m>n$ 時，$A^{m}_{n} = C^{m}_{n}=0$

組合數性質

\[C^{m}_{n} = C^{m}_{n-m}\tag1 \]

這是顯然的，從 $n$ 個元素中挑 $m$ 個元素拿出來等價于從 $n$ 個元素中挑 $n-m$ 個元素放在原地

\[C^{m}_{n} = \frac{n!}{m!(n-m)!} = \frac{n}{m} \times \frac{(n-1)!}{(m-1)![(n-1)-(m-1)]!} = \frac{n}{m} \times C^{m-1}_{n-1}\tag2 \]

小組合數簡單遞推式

\[C^{m}_{n} = C^{m}_{n-1}+C^{m-1}_{n-1}\tag3 \]

組合數遞推式，是 $(2)$ 的變式，證明如下

\[C^{m}_{n} = \frac{n}{m} \times C^{m-1}_{n-1} = (1 + \frac{n-m}{m}) \times C^{m-1}_{n-1} = \frac{n-m}{m} \times C^{m-1}_{n-1} + C^{m-1}_{n-1}\\ = \frac{n-m}{m} \times \frac{(n-1)!}{(m-1)!(n-m)!} + C^{m-1}_{n-1} = \frac{(n-1)!}{m!(n-m-1)!} + C^{m-1}_{n-1} = C^{m}_{n-1}+C^{m-1}_{n-1} \]

如何理解這個柿子？考慮其組合意義，選擇 $n$ 中的一個元素為“特殊元素”；當選出的 $m$ 個元素包含特殊元素時，只需另外從非特殊的 $n-1$ 個元素中選 $m-1$ 個元素，方法數為 $C^{m-1}_{n-1}$；當選出的不包含特殊元素時，即從非特殊的 $n-1$ 個元素中選擇 $m$ 個，方法數為 $C^{m}_{n-1}$

楊輝三角

楊輝三角是二項式系數在三角形上的幾何體現 (二項式系數指 $(a+b)^n$ 各項的系數，二項式定理后面再講)，同時也形象地表現出了組合數遞推式

C(0,0)=1
C(0,1)=1 C(1,1)=1
C(0,2)=1 C(1,2)=2 C(2,2)=1
C(0,3)=1 C(1,3)=3 C(2,3)=3 C(3,3)=1
C(0,4)=1 C(1,4)=4 C(2,4)=6 C(3,4)=4 C(4,4)=1
……

我們發現第 $i$ 行 $j$ 列的數就是 第 $\bm{i-1}$ 行 $\bm{j-1}$ 列的數與第 $\bm{i-1}$ 行 $\bm{j}$ 列的數之和，這就是組合數遞推式

P2822

如果我們在每一步都暴力階乘求解組合數，時間開銷無法接受；題目問的是從 $0$ 開始一個范圍內所有的組合數，因此可以使用組合數遞推式配合前綴和求出每一行所有滿足要求的組合數的數量

注意需要取模，可以邊求邊模，模之后為 $0$ 則代表當前組合數符合要求，此時更新前綴和即可

Lucas 定理

Lucas 定理用于求解大組合數取模問題，模數 $p$ 必須為素數，定理內容如下 (證明略)

\[C^{m}_{n} \bmod p = C^{\lfloor m/p \rfloor}_{\lfloor n/p \rfloor} \times C^{m \bmod p}_{n \bmod p} \bmod p \]

使用定理后可以直接求解 $\displaystyle C^{m \bmod p}_{n \bmod p}$，對于 $C^{\lfloor m/p \rfloor}_{\lfloor n/p \rfloor}$ 可以繼續遞歸求解

使用 Lucas 定理時，模數 $p$ 的范圍不能太大，一般在 $1e5$ 左右；遞歸到 $m=0$ 時返回 $1$ 即可

P3807

盧卡斯定理模板題，直接套定理即可，需要用常見技巧 預處理階乘，不然會 TLE

插板法

~~死去的小奧突然開始攻擊我~~

插板法可以求解相同元素分組問題與不定方程解數問題

1. 正整數解個數

求將 $n$ 個完全相同的元素劃分為 $k$ 組，每組至少有 $1$ 個元素的方法數；$n$ 個元素產生了 $n-1$ 個"空"，劃分為 $k$ 組需要放 $k-1$ 個板子，因此答案為 $C^{k-1}_{n-1}$

問題等價于求 $x_1+x_2+\cdots+x_k=n$ 的正整數解組數

2. 非負整數解個數

求將 $n$ 個完全相同的元素劃分為 $k$ 組，每組至少有 $0$ 個元素的方法數；按照"板子可以插在一起"這種思路不太好想，可以考慮將 全部 $\bm{k}$ 組每組增加一個元素，把非負整數解變成正整數解；這樣問題轉化為將 $n+k$ 個元素劃分為 $k$ 組的正整數解，答案為 $C^{k-1}_{n+k-1} = C^{n}_{n+k-1}$

問題等價于求 $x_1+x_2+...+x_k=n$ 的非負整數解數

3. 不同下界整數解個數

求將 $n$ 個完全相同的元素劃分為 $k$ 組，每組至少有 $a_k (\sum a_k \le n)$ 個元素的方案數；仿照上個情況的思想，將第 $k$ 組減少 $a_k$，將問題轉化為將 $n-\sum a_k$ 個元素劃分為 $k$ 組的非負整數解，答案為 $C^{k-1}_{n-\sum a_k+k-1} = C^{n-\sum a_k}_{n-\sum a_k+k-1}$

問題等價于求 $x_1+x_2+\cdots+x_k=n$ 的解數，其中 $x_i \ge a_i$

4. 不相鄰的排列個數

求從 $1 \sim n$ 選出 $k$ 個互不相鄰的整數的方案數；考慮先把 $k$ 個元素拿出來，再在這些元素中間添加一些元素使得其不相鄰，拿出來的元素中間形成了 $k-1$ 個 下界為 $\bm{1}$ 的空，頭尾各有一個 下界為 $\bm{0}$ 的空，總共有 $k+1$ 個空，答案為 $C^{k+1-1}_{n-k+1+1-1} = C^{k}_{n-k+1}$

P1771

求不定方程正整數解數模板題

P5520

可以直接套用 $4.$ 的公式；注意櫻花樹幼苗互不相同，因此答案需要多乘上 $m!$，為 $C^{m}_{n-m+1} \times m! = A^{m}_{n-m+1}$，不需要計算逆元了，直接邊乘邊模即可

3. 錯排列與圓排列

錯排列

對于 $1 \sim n$ 的排列 $P$，若 任意 $\bm{P_i}$ 都滿足 $\bm{P_i \ne i}$，則稱其為錯排列；舉個栗子，三元錯排列有 $\{2, 3, 1\}$ 與 $\{3, 1, 2\}$

錯排問題 (或稱郵差問題)，指給定 $n$，求 $n$ 元錯排列 $D_n$ 的個數；已知 $D_1=0, D_2=1$，仿照組合數遞推式的推導方法，我們考慮其遞推，有兩種情況

1. 前 $\bm{n-1}$ 個元素全部錯排

此時前 $n-1$ 個元素全部滿足要求，只需處理不合法的第 $n$ 個元素；我們希望第 $n$ 個元素改變位置，那么可以將其 與前面的元素交換，容易發現任意交換都滿足要求，因此方案數為 $(n-1) \times D_{n-1}$

2. 前 $\bm{n-1}$ 個元素有 $\bm{1}$ 個在其本來位置上，另外 $\bm{n-2}$ 個元素全部錯排

設前 $n-1$ 個元素中在其本來位置上的元素為 $i$，此時我們 交換第 $\bm{i}$ 個與第 $\bm{n}$ 個元素，也能得到合法的方案；由于不合法的元素 $i$ 可以任取，方案數即為 $(n-1) \times D_{n-2}$

最終，我們得到了錯排問題遞推式

\[D_n = (n-1) \times (D_{n-1}+D_{n-2})\tag1 \]

其實錯排問題還有其他遞推式，常見的還有

\[D_n = nD_{n-1} \times (-1)^n\tag2 \]

下面給出證明，考慮作差，帶入 $(1)$ 式，即得證

\[D_n-nD_{n-1} = (n-1) \times (D_{n-1}+D_{n-2}) - nD_{n-1}\\ = -[D_{n-1}-(n-1)D_{n-2}]\\ = (-1)^2[D_{n-2}-(n-2)D_{n-3}]\\ = ... = (-1)^{n-2}[D_2-2D_1] = (-1)^n \]

最后再不加證明地給出一個錯排數通項公式

\[D_n = \lfloor \frac{n!}{e} \rfloor\tag3 \]

P4071

錯排問題稍加變化，題意為求 $1 \sim n$ 的排列中恰好有 $m$ 個數在自己本來的位置上的方案數；首先先選出在自己位置上的 $m$ 個數，由于順序固定，有 $C^{m}_{n}$ 種選法；對于剩下的 $n-m$ 個數，我們可以按照大小關系類似地視為 $1 \sim n-m$ 的錯排列數，即 $D_{n-m}$

那么所求即為 $C^{m}_{n} \times D_{n-m}$；實現時，預處理階乘 + 費馬小定理求逆元求組合數，再按照上文提到的遞推公式求錯排列數即可

圓排列

$n$ 個元素排列成一個環形的不同方法數記為 $Q^n_{n}$，我們稱兩個圓排列相同當且僅當 所取元素相同 且元素 在環上的排列順序一致

考慮直線排列與圓排列的關系，假設我們已經知道了所有要填入的元素及排列順序，一共有 $n$ 個位置；首先在圓上按順序填好元素，接下來我們可以通過多次旋轉使得元素保持排列順序不變；容易發現最多能夠不重復地轉 $n$ 次，因此一個圓排列實際上對應 $n$ 種不同的直線排列

圓排列 $Q^{n}_{n}$ 的計算公式即為

\[Q^{n}_{n} = \frac{A^{n}_{n}}{n} = (n-1)! \]

我們可以對結論進行推廣，即 部分圓排列，求從 $n$ 個元素中選 $m$ 個排成環形的不同方法數，記為 $Q^{m}_{n}$

依照上面的思路，此時一個部分圓排列對應 $m$ 個直線排列，部分圓排列 $Q^{m}_{n}$ 的計算公式即為

\[Q^{m}_{n} = \frac{A^{m}_{n}}{m} = \frac{n!}{m \times (n-m)!} = \frac{n!(m-1)!}{m!(n-m)!} = C^{m}_{n} \times (m-1)! \]

CF1957E

題意為求 $\displaystyle \sum^{n}_{i=1} \sum^{i}_{j=1} C(i, j)$，其中 $C(i, j)$ 表示從 $i$ 個元素中選 $j$ 個的不同圓排列數

根據上文所述公式，有 $\displaystyle C(i, j) = C^{j}_{i} \times (j-1)!$；注意到式子中帶有 $\bmod j$，因此我們考慮求和換序，將原式變形為求 $\displaystyle \sum^{n}_{j=1} \sum^{n}_{i=j} (C^{j}_{i} \times (j-1)! \bmod j)$

確定 $j$，根據數據范圍，不難得知我們需要在不劣于 $O(\log n)$ 的時間復雜度內求出 $\sum^{n}_{i=j} (C^{j}_{i} \times (j-1)! \bmod j)$，考慮將其拆為兩部分求解

首先考慮 $(j-1)! \bmod j$；當 $j$ 非素數時，令 $j = a \times b\ (2 \le a,b \le \frac{j}{2})$，我們進行分類討論：

$a \ne b$，顯然 $a$ 與 $b$ 都被包含在 $(j-1)!$ 內，此時貢獻為 $0$
$a = b$ 且 $a \times 2 \ne j$，顯然 $2 \times a$ 與 $b$ 都被包含在 $(j-1)!$ 內，此時貢獻依然為 $0$
$a = b$ 且 $a \times 2 = j$，此時 $a=b=2, j=4$；由于 $3! \bmod 4 = 2$，此時貢獻為 $2$

對于 $j$ 非素數的情況，只有 $j=4$ 時會對答案產生貢獻，因此當 $j=4$ 時直接暴算所有 $C^{4}_{i}$ 即可

當 $j$ 為素數時，該式子即為 Wilson 定理，此時有$(j-1)! \bmod j = -1$，下面考慮此時如何計算 $\sum^{n}_{i=j} C^{j}_{i} \bmod j$；注意到組合數上恰有一個 $j$，是模數的倍數，這提醒我們可以使用 Lucas 定理進行簡化；由 Lucas 定理，$\displaystyle C^{j}_{i} \bmod j = C^{1}_{ \lfloor i/j \rfloor} \times C^{0}_{i \% j} \bmod j = \lfloor i/j \rfloor \bmod j$

因此，對于 $i \in [k \times j, (k+1) \times j - 1]$，其貢獻均為 $k$；我們可以枚舉每個 $k$，將對應區間加上 $(-k \bmod j)$；進一步，我們可以將區間加轉為差分解決，最終進行兩次前綴和即可 (差分與求 $\sum j$ 各需要一次前綴和)

4. 抽屜原理 (鴿籠原理)

將 $n+1$ 個元素劃分為 $n$ 組，則必然有一組至少有 $2$ 個元素；對其進行推廣，將 $n$ 個元素劃分為 $k$ 組，則必然有一組元素至少有 $\lceil \frac{n}{k} \rceil$ 個

UVA11237

首先將給定的 $a_i$ 全部模上 $c$，問題轉化為構造一個位置集合 $S$ 使得 $(\sum_{i \in S} a_i) \bmod c = 0$；求得 $a_i$ 的前綴和 $s_i$，顯然若 $s_i=0$，則 $S=\{1,2,3,\cdots,i\}$ 即滿足要求；除掉 $s_i=0$ 的情況，$s_i$ 的所有可能取值有 $c-1$ 種，又因為題目保證 $c \le n$，根據抽屜原理，必然至少有一對 $\bm{s_i}$ 的取值相同；設其為 $s_p, s_q (p \le q)$，則 $S=\{p+1,p+2,\cdots, q\}$ 滿足要求

綜上，一定可以證明存在一些連續的位置滿足要求，直接從前往后掃一遍即可

5. 二項式定理

二項式定理與二項展開式系數相關，定理內容為

\[(a+b)^n = \sum^{n}_{i=0} C^{i}_{n}a^{n-i}b^i \]

二項式定理證明

組合相關證明：

打開 $(a+b)^n$ 為 $(a+b) \times (a+b) \times ... \times (a+b)$，一共有 $n$ 項；每一項我們可以選擇貢獻 $a$ 或貢獻 $b$，若要湊出 $a^{n-i}$，需要從 $n$ 項中選擇 $n-i$ 個，方法數為 $C^{n-i}_{n}=C^{i}_{n}$；因此，$a^{n-i}b^i$ 項的系數為 $C^{i}_{n}$

數學歸納法證明：

在 $n=1$ 時，$(a+b)^1 = C^0_1a^1b^0+C^1_1a^0b^1$ 顯然成立

不妨設 $n=m$ 時定理成立，即有

\[(a+b)^m = \sum^{m}_{i=0} C^{i}_{m}a^{m-i}b^i \]

在 $n=m+1$ 時，有

\[(a+b)^{m+1} = (a+b) \times (a+b)^{m}\\ = (a+b) \times \sum^{m}_{i=0} C^{i}_{m}a^{m-i}b^i \]

將 $a$ 與 $b$ 合并進去

\[= a \times \sum^{m}_{i=0} C^{i}_{m}a^{m-i}b^i + b \times \sum^{m}_{i=0} C^{i}_{m}a^{m-i}b^i\\ = \sum^{m}_{i=0} C^{i}_{m}a^{m-i+1}b^i + \sum^{m}_{i=0} C^{i}_{m}a^{m-i}b^{i+1} \]

分離出 $C^0_m$ 與 $C^m_m$ 兩項，對其進行變形

\[= C^0_ma^{m+1}b^0 + \sum^{m}_{i=1} C^{i}_{m}a^{m-i+1}b^i + \sum^{m-1}_{i=0} C^{i}_{m}a^{m-i}b^{i+1} + C^m_ma^0b^{m+1}\\ = C^0_{m+1}a^{m+1}b^0 + \sum^{m}_{i=1} C^{i}_{m}a^{m-i+1}b^i + \sum^{m-1}_{i=0} C^{i}_{m}a^{m-i}b^{i+1} + C^{m+1}_{m+1}a^0b^{m+1}\\ = C^0_{m+1}a^{m+1}b^0 + \sum^{m}_{i=1} C^{i}_{m}a^{m-i+1}b^i + \sum^{m}_{i=1} C^{i-1}_{m}a^{m-i+1}b^{i} + C^{m+1}_{m+1}a^0b^{m+1} \]

根據組合數遞推式 $C^m_n = C^m_{n-1}+C^{m-1}_{n-1}$，對求和柿子進行合并

\[= C^0_{m+1}a^{m+1}b^0 + \sum^{m}_{i=1} C^{i}_{m+1}a^{m+1-i}b^i + C^{m+1}_{m+1}a^0b^{m+1}\\ = \sum^{m+1}_{i=0} C^{i}_{m+1}a^{m+1-i}b^i \]

證畢

二項式定理推論

\[C^{0}_{n} + C^{1}_{n} + ... + C^{n}_{n} = \sum^{n}_{i=0} C^i_n = 2^n\tag1 \]

為 $a=b=1$ 時，即取 $(1+1)^n$ 時的特殊情況

\[\sum^{n}_{i=0} (-1)^iC^i_n = [n=0]\tag2 \]

為 $a=1,b=-1$ 時，即取 $(1+(-1))^n$ 時的特殊情況，注意 $n=0$ 時原式值為 $1$

二項式定理例題

P1313

二項式定理板子題；由二項式定理，$(ax+by)^k$ 中 $x^ny^m$ 項的系數即為 $C^m_k a^{k-m} b^m$

CF1332E

容易發現，只要所有格子的奇偶性相同，一定可以達到目標，與格子上有多少方塊無關；本質上，我們 只需要考慮奇偶性

題目中操作 $1$ 只能使相鄰的兩格奇偶同時變化；實際上可以對該操作進行推廣，任取兩格 $p, q$ 與這兩格間的一條路徑 $p \rightarrow a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_n \rightarrow q$ (格子 $p$ 與 $a_1$，$a_i$ 與 $a_{i+1}$，$a_n$ 與 $q$ 均相鄰)，依次對路徑上相鄰的兩格進行一次操作 $1$，即依次操作 $(p, a_1), (a_1, a_2), \cdots, (a_n, q)$；最終 $a_1, a_2, \cdots, a_n$ 上的值都恰好 $+2$，奇偶性不變，$p, q$ 上的值都恰好 $+1$，奇偶同時變化；因此，操作 $1$ 可以更改為選擇任意兩格使其奇偶性同時變化

我們對 $n \times m$ 的奇偶性進行分討

$n \times m$ 為奇數；不妨設格子中填入了 $k_1$ 個奇數，$k_2$ 個偶數，有 $k_1 + k_2 = n \times m$，因此 $k_1$ 與 $k_2$ 必然有一個為偶數；這樣我們可以把這偶數個奇數 (或偶數個偶數) 全部通過操作 $1$ 變成偶數 (或奇數)，再通過操作 $2$ 達到目標；因此，此時隨便一種填法都滿足要求，方案數為 $(R-L+1)^{nm}$
$n \times m$ 為偶數；仍然設格子中填入了 $k_1$ 個奇數，$k_2$ 個偶數，有 $k_1 + k_2 = n \times m$；注意到操作 $1$ 與操作 $2$ 不改變所有格子上方塊數之和的奇偶性，而最終方塊數之和必然為偶數，因此若 $k_1 \bmod 2 =1$，顯然是不成立的；若 $k_1 \bmod 2 = 0$，則我們可以使用操作 $1$ 將所有的奇數變為偶數，即成立

因此，當 $n \times m$ 為奇數時可以 任意填入，方案數為 $(R-L+1)^{nm}$

當 $n \times m$ 為偶數時 必須填入偶數個奇數，在 $n \times m$ 個格子中選擇 $k$ 個格子的方案數為 $C^k_{nm}$，設 $[L, R]$ 中有 $p$ 個奇數、$q$ 個偶數 ( $p+q = R-L+1$ )，則單次方案數為 $C^k_{nm} p^kq^{nm-k}$，將所有 $k$ 為奇數的方案累加即為總方案數

我們觀察到這個柿子很像二項式定理，問題是 $k$ 一次會 $+2$ 而非 $+1$；我們考慮補全式子再減去多的部分，容易聯想到二項式定理推論 $(2)$，答案即為

\[\frac{\sum^{nm}_{k=0} C^k_{nm}p^kq^{nm-k} - \sum^{nm}_{k=0} (-1)^kC^k_{nm}p^kq^{nm-k}}{2}\\ = \frac{(p+q)^{nm} - (p-q)^{nm}}{2} \]

直接快速冪即可，時間復雜度 $O(\log(nm))$

6. 容斥原理

設有 $n$ 種不同的屬性，擁有第 $i$ 種屬性的元素集合為 $S_i$，則有

\[\begin{aligned} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\ &+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n| \end{aligned} \]

其中 $\cap$ 表示集合交運算，$\cup$ 表示集合并運算

另一種表達為

\[\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| \]

可以理解為逐層去掉重復的部分，再補回多減的部分

容斥原理證明

對于任一元素 $P_i$，設其出現在了集合 $S_1, S_2, \cdots S_m$ 中，則其被統計的次數為

\[C^1_m-C^2_m+\cdots+(-1)^{m-1}C^m_m \]

為什么呢？相當于我們分別統計 $|S_i|, |S_i \cap S_{j}|, \cdots$ 產生的貢獻，元素在其中任一個集合交結果中的出現次數都是 $1$，則不考慮正負系數情況下貢獻也是 $1$，因此可以直接統計怎么選

觀察到柿子很像二項式定理推論 $(2)$，嘗試進行變形

\[C^1_m-C^2_m+\cdots+(-1)^{m-1}C^m_m\\ = C^0_m - \sum^{m}_{i=0} (-1)^iC^i_m\\ = 1 - (1-1)^m = 1 \]

則每個元素剛好被統計一次，證畢

容斥原理推論

設全集為 $U$，若求全集中不具有任一性質的元素的個數，則有篩法公式

\[\left|\bigcap_{i=1}^{n} \overline{S_i} \right| = \left|U\right|-\left|\bigcup_{i=1}^{n}S_i\right|\tag1 \]

其中 $\overline{S}$ 表示集合 $S$ 的補集 (補集 $\overline{S}$ 是由 $U$ 中所有不屬于 $S$ 的元素組成的集合)

若求集合的交，可以用 全集減去補集的并集，證明顯然

\[\left|\bigcap_{i=1}^{n}S_i\right| = \left|U\right| - \left|\bigcup_{i=1}^{n}\overline{S_i}\right|\tag2 \]

公式 $(1), (2)$ 右側均可以使用容斥原理進一步變形

容斥原理例題

P1450

其實這題乍一看很像插板，但是實際上這題 限制了上界而非下界，第 $i$ 種硬幣最多能取 $d_i$ 個，因此考慮容斥

我們令屬性 $P_i$ 表示限制第 $i$ 種硬幣取的數量 $\le d_i$，同時其他硬幣取的數量可以為任意非負整數；記集合 $S_i$ 包含所有擁有屬性 $P_i$ 的選擇方法，答案即為

\[\left|\bigcap_{i=1}^{n}S_i\right| \]

可以先用容斥原理推論 $(2)$ 將其變形為

\[\left|\bigcap_{i=1}^{n}S_i\right| = \left|U\right| - \left|\bigcup_{i=1}^{n}\overline{S_i}\right| \]

其中 $\overline{S_i}$ 擁有的屬性即為：限制第 $i$ 種硬幣最少取 $d_i+1$ 個，同時其他硬幣取的數量可以為任意非負整數；這可以應用插板法的思想 —— 減去多出的下界 來解決

另外對于求容斥中一些集合 $\overline{S_{a_i}}$ 的交，可以轉化為以下不定方程的解數

\[\sum^4_{i=1} C_id_i = S - \sum^k_{i=1}C_{a_i}(d_{a_i}+1) \]

其中 $S$ 為要達到的目標；而 $S - \sum^k_{i=1}C_{a_i}d_{a_i}$ 為一個可以算出來的值，顯然這是可以預處理的，這樣就做完了

預處理時間復雜為 $O(4S)$，詢問時間復雜度為 $O(2^4n)$，總時間復雜度為 $O(4S+2^4n)$

P5664

簡要題意為給定一個 $n$ 行 $m$ 列的矩陣 $a[i][j]$ ，在其中選取 $k$ 行，每行只能取一個元素，每列最多取 $\lfloor \frac{k}{2} \rfloor$ 個元素；一種選法的貢獻為所有被選的元素之積，最終求所有選法的貢獻和

每列最多取 $\lfloor \frac{k}{2} \rfloor$ 個元素的限制其實不是特別好處理，考慮反面；我們觀察到 最多只有一列 能夠超出限制，因此直接枚舉該列即可，將其記為 $col$

不妨設選擇的方案中在 $col$ 列上選了 $res_1$ 個，其他列上選了 $res_2$ 個；如何判斷當前列超出限制？由于此時總數 $k$ 即為 $res_1+res_2$，因此直接判斷是否有 $res_1>res_2$ 即可

考慮 $dp$；由于我們 只關心 $\bm{res_1}$ 與 $\bm{res_2}$ 的大小關系，令 $dp[i][j]$ 表示當前考慮到第 $i$ 行，$res_1 - res_2 = j$ 的總方法數；對于第 $i$ 行，我們有三種處理方式：

不在這一行選擇任何元素；此時 $dp[i][j] += dp[i-1][j]$
在這一行的第 $col$ 列選擇元素，上一行的 $res_1 - res_2$ 應該減少 $1$；此時 $dp[i][j] += dp[i-1][j-1] \times a[i][col]$
在這一行的其他列選擇元素，上一行的 $res_1 - res_2$ 應該增加 $1$；此時 $dp[i][j] += dp[i-1][j+1] \times (\sum_{t \ne col} a[i][t])$

初始條件即什么都不選時，$dp[0][0]=1$

實現時，$\sum_{t \ne col} a[i][t]$ 可以預處理，另外注意 $res_1-res_2$ 可能小于 $0$，可以將第二維全部向右偏移 $n$；統計答案時累加所有第二維為正的結果即可，即 $\sum^{n+n}_{i=n+1} dp[n][i]$

對于總貢獻，我們也能夠采用類似的 $dp$ 策略，設 $total[i][j]$ 表示到第 $i$ 行總共選擇了 $j$ 個數的方法數；類似的，轉移為 $total[i][j] += total[i-1][j]$ 或 $total[i][j] += total[i-1][j-1] \times \sum^{n}_{t=1} a[i][t]$；

初始條件為 $dp[i][0]=1$，表示到第 $i$ 行全部都不選

實現時，求和仍然可以預處理，統計答案時累加即可，即為 $\sum^{n}_{i=1} total[n][i]$

P2567

相比上一題，這道的容斥味就很濃了

首先，我們預處理出所有 互不為倍數 的幸運號碼，為下一步容斥做準備；為什么要求互不為倍數？因為如果一個數既是幸運號碼又是近似幸運號碼，我們只需統計其作為近似號碼的貢獻，避免重復；實現時直接用 bfs 即可，總情況不超過 $2^{10}$

實際上，去掉不符合條件的數后一共有 $943$ 個幸運號碼；如果按照硬幣購物的思路，我們需要從 $1$ 枚舉到 $2^{943}$，顯然是不可取的；觀察到這些情況中有不少是不會產生貢獻的，具體的，設我們統計 $a_1, a_2,\cdots, a_n$ 這些幸運號碼在 $[a, b]$ 中的公倍數個數，若 $lcm(a_1, a_2, \cdots, a_n) > b$ 顯然就不會有任何貢獻

因此，我們考慮改用 dfs；仍然維護當前的 $pos$ (走到哪一步)，$lcm(a_i)$ (所有已選幸運號碼的公倍數) 與 $cnt$ (表示已經選了多少個幸運號碼)，當走到結尾時，貢獻即為 $\displaystyle \lfloor \frac{lcm(a_i)} \rfloor - \lfloor \frac{a-1}{lcm(a_i)} \rfloor$

別忘了在公倍數 $ > b$ 時進行剪枝；實現時，我們可以先將幸運號碼 從大到小排序，使不合法情況盡早出現。另外注意 $lcm$ 可能爆 long long，可以開 int128 或者變 long double 解決

~~時間復雜度不會算~~，但是由于 $lcm$ 的增長速度很快，應該沒什么問題

P5123

觀察到位置數只有 $5$，因此我們考慮對于每一頭牛，對其與之前的牛的重復號碼位置進行容斥

仍然使用類似硬幣購物的思路，用一個取值范圍為 $[1, 2^5-1]$ 的二進制數代表每位選/不選，判斷每位是否為 $1$ 即可

那么我們如何判斷選出的數與之前產生重復？有一種很暴力的想法就是開五個套起來的 map，第 $i$ 個套 $i$ 層，處理選擇 $i$ 個數的情況；但這么做很麻煩，其實有一個更好的辦法：哈希。注意，由于統計答案時本質上是無序的，但選擇的順序會影響哈希的結果，因此需要 先對給出的號碼進行排序

實現時，可以使用多項式哈?；蛘咧苯愚D成字符串再哈希；若使用多項式哈希記得把進制數開大點，同時建議使用自然溢出，~~我被卡了好幾次~~

P5505

我們設屬性 $P_i$ 表示：有 $i$ 名同學一定沒有特產，其余 $n-i$ 名同學可能有特產也可能沒有特產的方法數；設集合 $S_i$ 包含所有滿足屬性 $P_i$ 的分配方法

顯然 $S_0$ 會包含 $S_1$，$S_1$ 會包含 $S_2$，$\cdots$，$S_i$ 會包含 $S_{i+1}$；因此我們考慮使用容斥去掉它們之間重疊的部分

那么假設確定一定沒有被分到特產的同學數 $p$，如何求出 $\left|S_p\right|$？這本質上就是 插板法。設 $k = n-p$，我們先選出 $k$ 個可能能夠分到特產的同學，有 $C^{k}_{n}$ 種選法；接下來等價于對于所有 $i (1 \le i \le m)$ 種特產求不定方程 $x_1 + x_2 + \cdots + x_k = a_i$ 的 非負整數解數，根據插板法即為 $C^{k-1}_{a_i+k-1}$；而每種特產間相互獨立，總方案數即為 $\displaystyle C^k_n \times \prod^{m}_{i=1} C^{k-1}_{a_i+k-1}$

回到總體上，類比容斥原理，其實這里的 $\left|S_p\right|$ 類似于所有選 $p$ 個集合交起來的結果之和，即 $\displaystyle \sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^pS_{a_i}\right|$；因此最終的答案即為 $\displaystyle \sum^{n-1}_{i=0} (-1)^i \left|S_i\right|$

實現時，預處理出階乘即可，另外注意取模不要取成負數；時間復雜度 $O(nm)$

7. 卡特蘭數

卡特蘭數定義為一個數列 $H_n$，其中 $H_0 = H_1 = 1$，有如下的遞推公式與組合公式

遞歸定義：

\[H_n = \sum^{n-1}_{i=0} H_{i}H_{n-1-i}\tag1 \]

遞推公式：

\[H_n = \frac{H_{n-1} \times (4n-2)}{n+1}\tag2 \]

組合公式 $(1)$：

\[H_n = \frac{C^n_{2n}}{n+1}\tag1 \]

組合公式 $(2)$：

\[H_n = C^n_{2n} - C^{n-1}_{2n}\tag2 \]

卡特蘭數證明

由遞歸定義推到組合公式需要用到生成函數等知識，具體證明過程可以參考神奇的卡塔蘭(Catalan)數

兩組合公式間互推是比較簡單的，如下

\[C^{n}_{2n} - C^{n-1}_{2n} = \frac{(2n)!}{n! \times n!} - \frac{(2n)!}{(n-1)! \times (n+1)!} = \frac{(2n)!}{n! \times n!} \times (1 - \frac{n}{n+1}) = \frac{C^n_{2n}}{n+1} \]

由組合公式，可以進而證明遞推公式

\[\frac{H_{n-1} \times (4n-2)}{n+1}\\ = \frac{C^{n-1}_{2(n-1)} \times (4n-2)}{n \times (n+1)}\\ = \frac{(2n-2)! \times (4n-2)}{(n-1)! \times (n-1)! \times n \times (n+1)}\\ = \frac{(2n)! \times 2}{(n-1)! \times (n+1)! \times 2n}\\ = \frac{(2n)!}{n! \times (n+1)!} = H_n \]

反過來，遞推公式一直迭代下去也可以得到組合公式

\[H_n = \frac{4n-2}{n+1} \times H_{n-1}\\ = \frac{4n-2}{n+1} \times \frac{4(n-1)-2}{n-1+1} \times H_{n-2}\\ = \cdots\\ = H_0 \times \prod^{n}_{i=1} \frac{4i-2}{i+1}\\ = 2^n \times \frac{1 \times 3 \times \cdots \times (2n-1)}{(n+1)!}\\ = \frac{(2n)!}{n! \times (n+1)!} = \frac{C^n_{2n}}{n+1} \]

那么這些公式就都是等價的

卡特蘭數應用

1. 不相交弦問題

給定圓上的 $2n$ 個點，求使得將其兩兩連接得到的 $n$ 條線段不相交的方法數

連接一對點，實際上會將整個圓切成兩半，接下來連接的每對點必然處于同一部分中；因此這就是一個完全相同的子問題，遞歸式為 $dp_n = \sum^{n-1}_{i=0} dp_{i}dp_{n-1-i}$，其中 $i$ 與 $n-1-i$ 的意義為切開后兩邊的點對數

注意到這是卡特蘭數的遞歸定義，因此答案即為 $H_n$

板子題：P1375

1.1 二叉樹計數

給定 $n$ 個點，求可以構造多少個不同的二叉樹

類似的，選擇一個點為根會把整棵樹切成左子樹和右子樹，變為完全相同的問題；設左子樹有 $i$ 個節點，右子樹有 $n-1-i$ 節點，則有 $dp_n = \sum^{n-1}_{i=0} dp_{i}dp_{n-1-i} = H_n$

1.2 凸多邊形的三角劃分

給定一個凸 $n+2$ 邊形，求用 $n-1$ 條不相交的直線連接起各對頂點，且這些直線互不穿過，將多邊形劃分成 $n$ 個三角形的方法數

同樣的，我們選取一條邊，枚舉其往哪個頂點 (與當前邊的兩頂點互異) 連邊；這會將原多邊形劃分為一個 $i+2$ 邊形與一個 $n-1-i+2$ 邊形，去掉 $+2$，實際上就是卡特蘭數

為什么 $(i+2)+(n-1-i+2) \ne n+2$？這是由于我們去掉了原多邊形的一條邊，又在多邊形內部連了兩條邊，因此比之前增加了一條邊

2. $\bm{\pm1}$ 數列問題

求有多少個由 $n$ 個 $+1$ 與 $n$ 個 $-1$ 構成的任意前綴和總是非負數的數列 $a_1, a_2, \cdots, a_{2n}$

我們考慮其反面情況，即求有多少個這種數列使得其存在前綴和是負數；不妨用 最靠前的 不合法位置來統計，即取一個 $m (1 \le m \le 2n)$，使得 $\sum^{m}_{i=1} a_i < 0$ 且對于任意 $1 \le k < m$，滿足 $\sum^{k}_{i=1} a_i \ge 0$

問題即轉化為求所有滿足如下條件的數列數量：

\[\begin{cases} \ a_1+a_2+\cdots+a_m < 0\\ \ a_1+a_2+\cdots+a_{2n} \ge 0\\ \end{cases} \]

我們注意到，由于 $m$ 是最靠前的不合法位置，那么一定有 $a_1+a_2+\cdots+a_m = -1$，這也可以推出 $a_{m+1}+a_{m+2}+\cdots+a_{2n} = 1$；因此，我們考慮 構造另一個長度為 $\bm{2n}$ 的數列 $\bm$，滿足當 $1 \le i \le m$ 時有 $b_i = -a_i$，當 $m < i \le 2n$ 時有 $b_i = a_i$

容易發現構造出的 $b$ 數列是和不合法的 $a$ 數列 一一對應 的；觀察其性質，易得 $b_i \in \{1, -1\}$ 且 $\sum^{2n}_{i=1} b_i = 2$，由此可以進一步推出 $b$ 中有 $n+1$ 個 $1$、$n-1$ 個 $-1$；

因此，$b$ 數列的數量 (即不合法的 $a$ 數列的數量) 為 $C^{n-1}_{2n}$；又由于總共有 $C^n_{2n}$ 種情況，滿足要求的 $a$ 數列就一共有 $C^{n}_{2n} - C^{n-1}_{2n}$ 種

這就是卡特蘭數的組合公式，所以求的仍然是 $H_n$

板子題：P1722

2.1 合法棧序列數量

有 $n$ 個元素，初始時棧為空，每次操作可以選擇 push 或 pop，求合法的操作序列數

將 push 操作看作 $+1$，pop 操作看作 $-1$ 即可

板子題：P1044

2.2 買票問題

有 $2n$ 個人來買票，$n$ 個人持有面值為 $k$ 的錢，另外 $n$ 個人持有面值為 $2k$ 的錢；一張票 $k$ 塊錢，限定每人只能買一張；售票處開始時沒有錢，求有多少種排隊方式使得售票處在任何時候不會找不出錢

將持有 $k$ 塊錢的人買票看作 $+1$，持有 $2k$ 塊錢的人買票看作 $-1$ 即可

板子題：P1754

2.3 格路計數

有一網格圖，每一步只能向上走或向右走，求從點 $(0, 0)$ 走到 $(n, n)$ 且不穿過直線 $y=x$ 有多少種走法

將向上走看作 $-1$，向右走看作 $+1$，等價于 $\pm 1$ 序列問題

其實也有另一種理解方法：考慮反面，用第一次解除 $y=x+1$ 的點 $P$ 統計每條不合法路徑，可以將點 $P$ 到終點的路徑按照 $y=x+1$ 翻轉，這樣每條不合法路徑的終點都是點 $(n-1, n+1)$

格路計數圖片

從 $n-1+n+1 = 2n$ 次向前/向上中選擇向前走的 $n-1$ 次，不合法路徑的條數即為 $C^{n-1}_{2n}$；類似的，總路徑數為 $C^{n}_{2n}$，答案即為 $C^{n}_{2n} - C^{n-1}_{2n} = H_n$

卡特蘭數例題

P2532

我們需要選取 $N$ 個鋼材搭建高度為 $N$ 的階梯，注意到一個鋼材不可能包含整個階梯 $\ge 2$ 階，因此 恰好一個階梯包含一階

我們嘗試將原問題劃分為同樣的子問題，考慮枚舉 含有整個階梯左下角 的鋼材的右上角在哪上，因為它能夠完全分開上下兩部分；注意到分開后恰形成了兩個完全相同的子問題，于是遞推式即為 $dp_i = \sum^{n-1}_{i=1} dp_idp_{n-1-i}$，可以結合下圖理解

P2532 圖片

初值顯然有 $dp_1 = 1$，答案實際上就是卡特蘭數 $H_n$

P1641

考慮轉化為格路計數

由于 $1$ 的數量必須大于等于 $0$ 的數量，我們設填入 $1$ 代表向前走一步，填入 $0$ 代表向上走一步；因此題目轉化為，從出發點 $(0,0)$ 走到終點 $(n, m)$ 不穿過直線 $y=x$ (也就是不碰到直線 $y=x+1$) 的方案數

使用類似的處理方法，我們考慮反面，將第一次穿過 $y=x$ 及以后的路徑按照直線 $y=x+1$ 翻轉；根據幾何知識，這樣的路徑的終點均為 $(n+1, m-1)$，與原來的不合法路徑一一對應

因此不合法路徑有 $C^{n+1}_{n+m}$ 條，總共有 $C^{n}_{n+m}$ 條，答案即為 $C^{n}_{n+m} - C^{n+1}_{n+m}$

P3200

事實上打表容易發現答案就是卡特蘭數

證明放在后面，先說實現；這題有個很坑的點在于不保證 $p$ 為質數，有可能沒有逆元。那么怎么求卡特蘭數？一種很樸素的想法是分解質因數 + EXCRT；這有點麻煩，事實上我們可以更加直接一點：處理出所有出現的質數及其指數，最終快速冪求乘積即可，這樣就繞過了除法

具體的，使用組合公式，答案即為 $\displaystyle \frac{C^{n}_{2n}}{n+1} = \frac{(2n)!}{n! \times (n+1)!} = \frac{\prod^{2n}_{i=n+2} i}{n!}$；對于每個乘數分解質因數，維護含有的質數的指數即可

接下來給出答案即為卡特蘭數 $H_n$ 的證明；分析性質，容易得出奇數項遞增、偶數項遞增 (廢話)，且 所有偶數項上的數都比其前面所有的數大，也就是 大于等于其下標

考慮從小到大依次填入 $1-2n$；由于填入的數嚴格遞增，奇數項與偶數項間不能出現"空著"的位置，即每個數只能填入最靠前的空著的奇數項或偶數項，同時也要滿足前面推出的對偶數項的限制

可能有點繞，舉個栗子：假設已經在第 $1$ 位填入 $1$、第 $2$ 位填入 $2$，$3$ 理論上可以填在第 $3$ 位上 (最靠前的奇數位) 也可以填在第 $4$ 位上 (最靠前的偶數位)，但由于 $3<4$，實際上它不能填在第 $4$ 位上

我們嘗試更具象地表述這一偶數項的限制；設我們目前填入了 $1-k$，令 $p_1$ 表示前面填入了多少個奇數項，$p_2$ 表示前面填入了多少個偶數項 ( $p_1+p_2=k$ )；顯然下標最大的偶數項值為 $val = 2 \times p_2$，那么需要滿足 $val \ge p_1+p_2$，也就是 $\bm{p_2 \ge p_1}$！

這個性質我們已經非常熟悉了，就是前面講過的 $\pm 1$ 問題，放在偶數項上視為 $+1$，放在奇數項上視為 $-1$，因此答案即為 $H_n$

P3978

記 $n$ 個節點形成的不同構二叉樹的葉子數量之和為 $f_n$，形成的不同構數量為 $H_n$ (就是卡特蘭數)，題意即為給定 $n$，求 $\frac{f_n}{H_n}$

事實上打表容易發現 $f_n = n \times H_{n-1}$

下面給出證明；我們考慮 $n$ 個節點的二叉樹與 $n-1$ 個節點的二叉樹間的遞推關系，顯然就是 $n-1$ 個節點的二叉樹又添了個節點 (廢話)；由于添上一個節點后形成的二叉樹必然有葉子 (還是廢話)，因此我們一定可以通過 將 $\bm{n}$ 個節點的二叉樹刪去一個葉子 覆蓋所有的 $n-1$ 個節點組成的二叉樹

所以 $f_n = H_{n-1}$ ...嗎？顯然不是；刪去一個葉子，得到的 $n-1$ 個節點組成的二叉樹可能重復；我們想要通過 $H_{n-1}$ 推到 $f_n$，就得知道第 $i$ 個 $n-1$ 個節點的二叉樹重復出現的次數 $p_i$，這樣就有 $f_n = \sum^{H_{n-1}}_{i=1} p_i$

那么為什么會造成重復？$n-1$ 個節點組成的二叉樹上可能能掛很多個葉子，刪掉這些掛上的不同的葉子就引起了重復；這樣問題轉化為 可以掛多少個葉子

不妨設原 $n-1$ 個節點組成的二叉樹上兒子數為 $0$ 的節點個數為 $num_0$，兒子數為 $1$ 的節點個數為 $num_1$，兒子數為 $2$ 的節點個數為 $num_2$；由于樹有 $n-1$ 個點 $n-2$ 條邊，容易得到以下關系式

\[\begin{cases} num_0 + num_1 + num_2 = n-1\\ 0 \times num_0 + 1 \times num_1 + 2 \times num_2 = n-2 \end{cases} \]

兩式相減，得到 $num_0 - num_2 = 1$；原二叉樹上兒子數為 $0$ 的點可以掛兩個葉子，兒子數為 $1$ 的點可以掛一個葉子，兒子數為 $2$ 的點不能掛葉子；因此總共能掛 $\bm{p_i = 2 \times num_0 + 1 \times num_1 + 0 \times num_2 = num_0 + num_1 + (num_2 + 1) = n}$ 個葉子

那么重復次數 $p_i$ 均為 $n$，即有 $f_n = n \times H_{n-1}$，得證

最終答案即為

\[\frac{f_n}{H_n} = \frac{n \times H_{n-1}}{H_n} = \frac{n \times (n+1) \times C^{n-1}_{2n-2}}{n \times C^{n}_{2n}} = \\\frac{(2n-2)! \times n! \times n! \times (n+1)}{(2n)! \times (n-1)! \times (n-1)!} = \frac{n \times n \times (n+1)}{(2n-1) \times 2n} = \frac{n^2+n}{4n-2} \]

8. 康托展開

給定一個 $\bm{1 \sim n}$ 的排列，將其按照字典序排序，可以使用康托展開求其排名

在一些問題中 (如之前做過的八數碼問題) 中，可以用康托展開進行狀態壓縮，方便判斷是否走到過；其實 FA 告訴我說這個東西之前汪老師講過，因此我就 ~~再講一遍~~

算法的過程其實還蠻好理解的；設我們當前處理排序后排列的第 $i$ 位 ($1 \le i \le n$)，當前位上的值為 $val[i]$；顯然，所有第 $i$ 位為 $1 \sim val[i]-1$ 的其他排列都在當前排列之前，除去第 $i$ 位上的數和之前填好的數，剩余的 $n-i$ 個數可以在后面的 $n-i$ 個位置中隨意排列，有 $\bm{(n-i)!}$ 種填法

接下來考慮第 $i$ 位能夠填什么；首先，它必須為 $1 \sim val[i]-1$ 中的一個數，這樣才能保證在當前排列前面；其次，它不能和之前填好的 $i-1$ 個數 (也就是 $val[1], val[2], \cdots, val[i-1]$) 相同。于是我們需要處理出 在 $\bm{1 \sim val[i]-1}$ 中有多少個數已經在前面被填入了，可以使用 樹狀數組 解決

設前面有 $k$ 個數已經被填入，貢獻即為 $(val[i]-1-k) \times (n-i)!$，從 $1$ 到 $n$ 枚舉 $i$，累加貢獻即可；注意這樣我們求出的是在當前排列前面的排列的數量，最終 還要 $\bm{+1}$

時間復雜度 $O(n \log n)$

P5367

康托展開模板

9. 多重集的排列數與組合數

多重集，顧名思義，本質上是廣義的集合，可以包含重復的元素；具體的，設多重集 $S$ 中一共含有 $n$ 個元素，有 $k$ 種不同元素，第 $i$ 種元素的值為 $v_i$、有 $c_i$ 個，則可以表示為 $S = \{c_1 \cdot v_1, c_2 \cdot v_2, \cdots, c_k \cdot v_k\}$

多重集的排列數

對于含有 $n$ 個元素、$k$ 種不同元素的多重集 $S = \{c_1 \cdot v_1, c_2 \cdot v_2, \cdots, c_k \cdot v_k\}$，其所有 $n$ 個元素的 全排列數 即為它們組成的多重集的組合數；這里不能直接簡單的用 $n!$ 計算，因為對于每 $c_i$ 個相同元素，這么算實際上 認為它們是互不相同的。本來這些元素只會產生 $1$ 個貢獻，這樣算會認為它們產生了 $c_i!$ 個貢獻；那么真實的結果應該是 $\displaystyle \frac{n!}{\prod^{k}_{i=1} c_i!}$

多重集的組合數

對于含有 $n$ 個元素、$k$ 種不同元素的多重集 $S = \{c_1 \cdot v_1, c_2 \cdot v_2, \cdots, c_k \cdot v_k\}$，在其中選出 $r$ 個元素的方案數即為多重集的組合數

若對于任意 $1 \le i \le k$ 都有 $r \le c_i$，問題即簡化為：枚舉 $i (1 \le i \le k)$，在第 $i$ 種元素中選擇 $x_i$ 個使得 $\sum^{k}_{i=1} x_i = r$ 的方案數；這就是之前講過的不定方程的非負整數解數，結果即為 $C^{k-1}_{r+k-1}$

考慮進行推廣；如果對 $r$ 沒有限制，又該如何求解？仍然考慮轉化為不定方程解數，即 $\sum^{k}_{i=1} x_i = r$，區別在于這里限制 對于任意 $\bm{1 \le i \le k}$，有 $\bm{x_i \le c_i}$；這其實和硬幣購物那題挺像的，由于限制下界容易解決，我們使用容斥原理將上界轉化為下界

具體的，設屬性 $P_i$ 表示限制 $x_i \le c_i$，且其他 $x_j (i \ne j)$ 都為非負整數；記集合 $S_i$ 包含所有擁有屬性 $P_i$ 的選擇方法，答案即為

\[\left|\bigcap_{i=1}^{k}S_i\right| \]

同樣使用容斥原理推論 $(2)$，變形為

\[\left|\bigcap_{i=1}^{k}S_i\right| = \left|U\right| - \left|\bigcup_{i=1}^{k}\overline{S_i}\right| \]

這里 $\left|U\right|$ 即為原不定方程的非負整數解數，易知為 $C^{k-1}_{r+k-1}$

使用容斥原理展開右側，我們還需要求一些補集的交；設這些補集為 $a_1, a_2, \cdots, a_p (1 \le p \le k)$，根據插板法，第 $a_i$ 個空的下界為 $c_{a_i}+1$ (注意要 $\bm{+1}$)，其余空的下界為 $0$，我們只需要減去多出的下界，轉化為求非負整數解數；那么這些補集的交即為 $C^{k-1}_{r-\sum^{p}_{i=1} (c_{a_i}+1)+k-1}$

最終根據容斥原理計算即可

CF451E

多重集的組合數 (推廣) 板子題

這里 $n$ 很小，$s$ 很大，算 $C^{n-1}_{s-\sum^{p}_{i=1} (f_{a_i}+1)+n-1}$ 的時候分子只有 $n-1$ 項，完全可以直接暴算，但注意乘數可能很大，需要提前取模；事實上我們求的所有組合數的分母都是 $(n-1)!$，因此可以 預處理逆元 進行優化

posted @ 2025-07-22 10:20 lzlqwq 閱讀(64) 評論(0) 收藏舉報

刷新頁面返回頂部