加法原理

加法原理。很直白的，就是一個用加法來弄的原理。

簡單來說，就是做一件事情有 \(n\) 種方法，第 \(i\) 種方法又有 \(a_i\) 個具體的操作方案。那么非常顯然，做這件事情就有 \(a_1 + a_2 + \dots + a_{n-1} + a_n = \sum_{i=1}^{n} a_i\) 種方案。

說說具體用途吧：最常見的，DP 里面統(tǒng)計方案數(shù)，由于這些解決方案是互不干擾的，也就是說如果選擇 \(1\) 類方法就不可能同時選擇 \(2\) 類方法，那么很多時候就是把它們加起來啦。

這就是加法原理。

乘法原理

乘法原理，顧名思義，和加法原理一樣，當然是用乘法來弄的原理啦！

乘法原理和加法原理不同，它表示的是，做一件事情有 \(n\) 個步驟，第 \(i\) 個步驟又有 \(a_i\) 種具體的操作方案，那么做這件事情一共就有 \(a_1 \times a_2 \times \dots a_{n-1} \times a_n = \prod_{i=1}^{n} a_i\) 中具體的操作方案。

用途吧，就是很多時候考慮統(tǒng)計方案數(shù)的時候，要分步驟來考慮——換言之，分類討論？——總之就是有一個分步驟的階段的情況下，就要用到乘法原理，把它們乘起來啦。

這就是乘法原理。

全排列

全排列表示有 \(n\) 個互不相同的物品，然后將這些物品全部打亂，重組地去排列，一共有多少種方法。答案顯然，\(n \times (n-1) \times (n-2) \times \dots \times 2 \times 1\)，定義這個東西為 \(n!\)，即 \(n\) 的階乘。

排列組合

排列，就是指從 \(n\) 個物品中選擇 \(m\) 個排成一排。假設它們都互不相同，那么方案數(shù)是多少呢？很顯然，排在第一個位置有 \(n\) 種選法，第二個位置有 \(n-1\) 種選法，第 \(i\) 個位置有 \(n-i+1\) 種選法，第 \(m\) 個位置有 \(n-m+1\) 種選法，全部乘起來，那就是 \(n \times (n-1) \times (n-2) \times \dots \times (n-m+1)\) 啦！這就定義為 \(A_{n}^{m}\)，且有公式 \(A_{n}^{m} = \dfrac{n!}{(n-m)!}\)。

組合，同樣是從 \(n\) 個物品中選擇 \(m\) 個，但是不同的是，它是選擇 \(m\) 個，但是只把這東西當做一個集合，并不對其進行排序——對，差別就在于，它比排列少考慮了具體的排序情況！這東西定義為 \(C_{n}^{m}\)，也記做 \(\binom{n}{m}\)，且有公式 \(C_{n}^{m} = \binom{n}{m} = \dfrac{n!}{(n-m)!\space{}m!}\)。對！就是比排列多除以了一個 \(m!\) 而已，因為不考慮順序啦。

組合還有一個公式，那就是 \(C_{n}^{m} = C_{n-1}^{m-1} + C_{n-1}^{m}\)，這也是求解楊輝三角時的遞推公式。為什么呢？因為我們已經(jīng)考慮完了前 \(n-1\) 個元素的情況，現(xiàn)在多了一個 \(n\) 元素，我們可以考慮選它，那么之前 \(n-1\) 個元素中就只需要選擇 \(m-1\) 個了，這就是 \(C_{n-1}^{m-1}\)，也可以考慮不選它，那么之前 \(n-1\) 個元素中還需要選擇 \(m\) 個，這就是 \(C_{n-1}^{m}\)，加法原理加起來就有公式 \(C_{n}^{m} = C_{n-1}^{m-1} + C_{n-1}^{m}\) 啦。

楊輝三角可以 \(O(n^2)\) 預處理出來，因此當 \(n\) 不大且需要使用組合數(shù)的時候常用楊輝三角預處理哦。

容斥

舉個簡單的例子，全班有 \(20\) 人，其中有 \(10\) 個人喜歡吃巧克力，\(15\) 個人喜歡吃冰淇淋，還有 \(2\) 個人什么都不喜歡吃，問有多少個人既喜歡吃巧克力又喜歡吃冰淇淋呢？很簡單，首先考慮把什么都不喜歡吃的 \(2\) 個人減掉，那么還剩 \(20-2=18\) 個人。\(10+15=25\)，如果不發(fā)生任何重疊的話還有 \(25\) 個人，但這顯然和 \(18\) 不吻合，因此拿 \(25 - 18 = 7\)，有 \(7\) 個人既喜歡吃巧克力又喜歡吃冰淇淋。

更常見的，比如說維恩圖這種，有三個集合 \(A,B,C\)，分別的大小都是 \(|A|,|B|,|C|\)，問它們的并集 \(A \cup B \cup C\) 的大小即 \(|A \cup B \cup C|\) 是多少。不難得出式子 \(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\)，畫圖會比較形象一些。如果延伸一下，大概就是，依次枚舉出現(xiàn) \(i\) 個數(shù)字，然后交集什么的，加起來，乘上 \((-1)^{i-1}\) 加進答案里。

容斥的運用挺廣泛的，很多題目都有它的影子，比如說有時候吧，我們求在滿足某某條件下的方案數(shù)，但是不好求，就可以改成是全部的方案數(shù)減去不滿足某某條件下的方案數(shù)，這樣就能算出來了，這就是正難則反，也是容斥最最基本、最最常見的運用了。有的時候可能要同時滿足兩個條件，那么就可以改成全部的方案數(shù)減去不滿足第一種條件的方案數(shù)再減去不滿足第二種條件的方案數(shù)最后再加上兩種方案都不滿足的方案數(shù)。確實，說起來挺繞口的，但這個東西就是上面講到過的容斥的一個思想，很常用的哈，甚至在某些 DP 啊圖論啊什么的題目里，都會融入一點點容斥的元素在里邊。

例題選講

題太多了，我就挑幾道重點講，其他的帶過一下好吧。

A - 盒子與球

Tag：階乘，DP。

定義 \(dp_{i,j}\) 表示考慮將 \(i\) 個球放入 \(j\) 個盒子的情況下有多少種方案。

轉(zhuǎn)移考慮兩種情況，一種是將球 \(i\) 新開一個盒子 \(j\) 放入，還有一種是從原先 \(j\) 個盒子中任意挑選一個放入球 \(i\)，加起來就是 \(dp_{i,j} = dp_{i-1,j-1} + j \times dp_{i-1,j}\)。

最后的答案就是 \(dp_{n,r}\)……嗎？不對，因為這里沒有考慮球的順序情況，而題目明確說明球是互不相同的，因此還要乘上 \(r!\) 才行，所以最終答案是 \(dp_{n,r} \times r!\)。

B - Permutation Warm-Up

Tag：打表找規(guī)律（？不是這對嗎）。

但是好像就是打個表……然后去研究一下整體的一個規(guī)律趨向。定義 \(S(x)\) 表示 $x + (x-2) + (x-4) + \dots $ 直到 \(0\)，也就是說當 \(x\) 為奇數(shù)的時候 \(S(x) = 1 + 3 + \dots + (x-2) + x\)，而當 \(x\) 為偶數(shù)的時候 \(S(x) = 2 + 4 + \dots + (x-2) + x\)。答案即為 \(S(n-1) + 1\)，為什么要 \(+1\) 呢，因為還有 \(0\) 的情況呀！

C - Having Been a Treasurer in the Past, I Help Goblins Deceive

Tag：貪心，簡單結論運用。

首先算一下原 \(s\) 中有多少個眼睛和多少個嘴巴，分別記為 \(Eye\) 和 \(Mou\)。

由于這個 -_- 由中間一個嘴巴和左右分別一個眼睛構成，為了最大化這個圖標的數(shù)量，考慮把所有嘴巴都放在中間，然后把眼睛放在兩邊。

易知如果在左邊放 \(x\) 個眼睛，右邊放 \(y\) 個眼睛（顯然有 \(x+y=Eye\)）的話，那么就有 \(Mou \times x \times y\) 個 -_-，為了最大化 \(x \times y\)，顯然考慮平均分 \(Eye\) 分布在左右兩邊，因此有 \(x = \lfloor \frac{Eye}{2} \rfloor\) 以及 \(y = Eye - \lfloor \frac{Eye}{2} \rfloor\)，最后輸出就好啦！

D - Replace Character

Tag：桶，貪心，構造。

首先考慮一個字符串會產(chǎn)生多少種排列數(shù)。假設 \(c_{\text{a}}\) 表示字符串中 \(\text{a}\) 出現(xiàn)的次數(shù)，\(c_{x}\) 表示字符串中 \(x\) 出現(xiàn)的次數(shù)，不難發(fā)現(xiàn)這個排列數(shù)為 \(\dfrac{n!}{c_{\text{a}}!c_{\text{b}}!\dots c_{\text{y}}! c_{\text{z}}!}\)。

由于題目希望操作后的字符串具有最小不同排列數(shù)，又因為這個操作等價于將某種字符的個數(shù) \(+1\) 再將某種字符的個數(shù) \(-1\)，不難貪心地想到將出現(xiàn)次數(shù)最小的字符的個數(shù) \(-1\)，再將出現(xiàn)次數(shù)最大的字符的個數(shù) \(+1\)，這樣能最大化上面多 \(\div\) 的值，因為如果將某種出現(xiàn)次數(shù)為 \(x\) 的字符的個數(shù) \(+1\) 再將某種出現(xiàn)次數(shù)為 \(y\) 的字符的個數(shù) \(-1\)，會將原來的排列數(shù) \(\times \dfrac{y}{x+1}\)，為了最小化 \(\dfrac{y}{x+1}\)，當然是選擇最大的 \(x\) 且最小的 \(y\) 啦。

因此用桶統(tǒng)計一下每種字母出現(xiàn)的次數(shù)，然后挑出最大最小進行一個修改，最后輸出就可以啦。

E - 數(shù)字串個數(shù)

Tag：快速冪，容斥。

由于這個人不喜歡數(shù)字 \(0\)，因此每一位都只能出現(xiàn) \(1 \sim 9\)，共 \(9\) 種數(shù)字，那么一共就有 \(9^{10000}\) 種情況。

由于必須存在 \(3\)，因此減去沒有 \(3\) 的情況數(shù) \(8^{10000}\)；同樣由于必須存在 \(7\)，因此減去沒有 \(7\) 的情況數(shù) \(8^{10000}\)。插一嘴題外話，這兩個數(shù)字正好也是我喜歡的，不過少了一個 \(5\)。

但是這樣的話既不存在 \(3\) 又不存在 \(7\) 的數(shù)字就被減了兩次了，要補回來一次，因此最后還要加上 \(7^{10000}\)。

所以答案為 \(9^{10000} - 8^{10000} - 8^{10000} + 7^{10000}\)，輸出即可。

F - 越獄

Tag：快速冪，容斥。

首先考慮所有關押的情況數(shù)，有 \(m^n\) 種。

接著考慮不會越獄的情況數(shù)——首先為第一個房間的人挑選一個宗教，有 \(m\) 種情況，那么接下來 \(n-1\) 個人為了不和前一個人同樣就只有 \(m-1\) 種選擇了，那么情況數(shù)就是 \(m \times (m-1)^{n-1}\)。

對這兩個東西做減法，\(m^n - m \times (m-1)^{n-1}\) 就是答案。

G - 煉金術（Alchemy）

Tag：快速冪，簡單思維。

插一嘴題外話，oymz 真的太強了，請教一下如何做到猜樣例猜對結論的。

考慮每一種金屬元素分別出自哪個熔爐。很顯然，有多個熔爐煉出這種金屬元素是沒有問題的，但是不能沒有熔爐煉出這種金屬元素。不難發(fā)現(xiàn)有 \(2^k - 1\) 種煉出金屬的熔爐的選擇方案——用二進制來考慮，\(1\) 表示煉出，\(0\) 表示沒有煉出。而因為有 \(n\) 種金屬元素，因此答案就是 \((2^k-1)^n\) 啦，寫個快速冪就完事兒了。

H - Kuro and Walking Route

Tag：分類討論，DFS，容斥。

首先跑一通 DFS，算出每個子樹的大小 \(sz_u\)。為了方便直接令 \(1\) 為根。

首先考慮最簡單的——\(X\) 和 \(Y\) 兩個點不構成任何祖先啥的關系，也就是說，\(X\) 不是 \(Y\) 的祖先，\(Y\) 也不是 \(X\) 的祖先，的情況下——很顯然，答案就是 \(n \times (n-1) - sz_X \times sz_Y\)。因為只有從 \(X\) 的子樹出發(fā)，到達 \(Y\) 的子樹，才會經(jīng)過 \(X\) 和 \(Y\) 這兩個點，因此簡單容斥即可。

接著考慮存在祖先關系的。這里只說明 \(X\) 是 \(Y\) 的祖先的情況，反過來是類似的。由于 \(X\) 是 \(Y\) 的祖先，因此肯定是要從外面什么地方進來，首先要進到 \(X\) 這棵子樹，然后再進入 \(Y\) 的子樹的情況。但是我們發(fā)現(xiàn)，答案 \(n \times (n-1) - (n-sz_X+1) \times sz_Y\) 是不對的，因為也有可能是本來就在 \(X\) 的子樹，但和 \(Y\) 不處于同一分叉的情況下，也是會先進 \(X\) 再到 \(Y\) 的，因此要找到 \(Y \to X\) 的這條路上經(jīng)過的倒數(shù)第二個節(jié)點，也就是 \(X\) 的兒子節(jié)點中唯一一個是 \(Y\) 的祖先的節(jié)點 \(K\)，答案 \(n \times (n-1) - (n-sz_K) \times sz_Y\) 才是正確答案。

I - 啟 · 破繭初陽

Tag：容斥，最大公因數(shù)和最小公倍數(shù)。

首先考慮一下——只是 \(a\) 的倍數(shù)的，只是 \(a\) 和 \(c\) 的倍數(shù)的，只是 \(b\) 和 \(c\) 的倍數(shù)的，只是 \(a\) 和 \(b\) 和 \(c\) 的倍數(shù)的，都要算進來——換句話說，只有只是 \(a\) 和 \(b\) 的倍數(shù)的，以及只是 \(b\) 的倍數(shù)的，被無情地攔在了門外不能被算進去。

這個東西畫個圖可能會形象一點啊，這里就文字描述了。其實是因為懶得畫圖 emm

那么怎么算呢？這里首先定義 \(S(x)\) 表示是 \(x\) 的倍數(shù)的數(shù)字個數(shù)，\(S(x,y)\) 表示既是 \(x\) 的倍數(shù)又是 \(y\) 的倍數(shù)的數(shù)字個數(shù)，同理定義 \(S(x,y,z)\) 表示既是 \(x\) 的倍數(shù)又是 \(y\) 的倍數(shù)還是 \(z\) 的倍數(shù)的數(shù)字個數(shù)，方便以下進行描述。

首先讓 \(Ans = S(a) + S(c)\)，但是這樣顯著多了，\(a\) 和 \(b\)，以及 \(a\) 和 \(c\) 的，都要減去，因此 \(Ans = S(a) + S(c) - S(a,b) - S(a,c)\)。但是這樣的話 \(a\) 和 \(b\) 和 \(c\) 的就被減沒了，因此還要加上 \(S(a,b,c)\) 才是最終的正確答案。

但是 \(S(x),S(x,y),S(x,y,z)\) 究竟都該怎么做呢？其實就是對這傳進來的幾個參數(shù)求個 \(\text{lcm}\)，那么就是 \(\lfloor \dfrac{n}{\text{lcm}} \rfloor\) 了。

題目很坑，三個數(shù)的 \(\text{lcm}\) 用 long long 存不下，要開 __int128。

J - Twin Polynomials

Tag：DP。

是的，我覺得這就是一個 DP 的一個思想。

首先考慮所有 \(a_i = -1\)，也就是所有 \(a_i\) 都沒有被定下來的情況。\(a_0\) 是不用考慮的，因此我們只考慮 \(a_{1 \sim n}\)。

發(fā)現(xiàn)一個式子，有 \(a_i = \sum_{a_j = i} j\)，并且對于所有 \(1 \le i \le n\)，最多也只能有一個 \(j\) 可以和它組成一個環(huán)組，也就是 \(a_i = j\) 且 \(a_j = i\)。

對于每個 \(a_i (1 \le i \le n)\)，都只有三種取值，要么 \(a_i = 0\)，要么 \(a_i = i\)，要么存在一個 \(j\) 使得 \(a_i = j\) 且 \(a_j = i\)。

定義 \(dp_i\) 表示當前考慮 \(i\) 個數(shù)進行匹配的情況。枚舉 \(i\)，考慮轉(zhuǎn)移。首先有這個值等于 \(0\) 或者自己本身的情況，那么有 \(dp_{i-1} \times 2\) 種情況；還有一種方法那就是從前面 \(i-1\) 個數(shù)字種選擇一個來和 \(i\) 組成環(huán)組，那么有 \(dp_{i-2} \times (i-1)\) 種情況；加起來得到轉(zhuǎn)移方程 \(dp_i = dp_{i-1} \times 2 + dp_{i-2} \times (i-1)\)。

現(xiàn)在考慮只存在部分 \(a_i = -1\) 的常規(guī)情況，首先把需要匹配的環(huán)組情況都搞定，發(fā)現(xiàn)不合法的直接輸出 \(0\)。

接著統(tǒng)計在 \(a_1 \sim a_{n-1}\) 中 \(-1\) 的數(shù)量，記為 \(cnt\)，考慮最終答案是多少。如果 \(a_n \not= -1\)，也就是說 \(a_n\) 的值已經(jīng)被固定了（可能是前面有值和它形成了環(huán)組），那么答案就是 \(dp_{cnt}\)；否則的話，還要考慮上 \(a_n\) 的情況——但答案可不是 \(dp_{cnt} \times 2 + dp_{cnt-1} \times cnt\) 而是 \(dp_{cnt} + dp_{cnt-1} \times cnt\)，為什么？因為題目明確說了，\(a_n\) 不能等于 \(0\)，因此就少一種情況啦！

時刻注意取模，不然會炸完。

總結

排列組合常用來出偏數(shù)論、數(shù)學這一塊的題目，也有些時候會融入 DP 或者圖論什么的元素，有時會用楊輝三角預處理組合數(shù)；并且很多需要使用組合數(shù)的題目，基本都和乘法逆元脫不了干系。而容斥的運用則更加廣泛，不僅在數(shù)論這個板塊頻繁顯身，很多時候都會隱藏在各種各樣的算法題目中——比如最經(jīng)典的“正難則反”，有哪些沒用到容斥？因此容斥是一個經(jīng)常出現(xiàn)的東西，不過這里有一個小小的坑，如果說要做減法但是取了模的話，一定要記得先加上模數(shù)再取一次模，不然可能會出現(xiàn)負數(shù)哦！

Thanks reading.