系統列舉與分類討論

這招在解什麼題

有些題目情況數其實有限，但條件太雜、套不上乾淨的排列組合公式。這時最可靠的武器是 系統列舉（systematic enumeration） 與 分類討論（casework）——不是亂數，而是有章法地把所有情況走一遍，保證不重不漏。

競賽裡它常是「別的技巧卡住時的保底解法」：只要列得夠有系統，再雜的限制也能一格一格數清楚。

核心：選一個「主軸」，依序固定

系統列舉的靈魂是選一個變數當主軸，讓它由小到大依序取值，每固定一個值，剩下的就變成更小的子問題。

例：三種貼紙各至少買 $1$ 張、剛好用 $40$ 點（紅 $3$、藍 $5$、金 $8$ 點）。以金貼紙張數為主軸，$1$ 張、$2$ 張、$\dots$ 依序固定，剩下的 $3\times\text{紅}+5\times\text{藍}=40-8\times\text{金}$ 就退化成一個二元問題，逐一數即可。

把主軸的每個取值攤開來看，「有序窮舉」到底在做什麼就一目了然：

主軸走到「金 $=5$」就停，因為剩下 $0$ 點卻還要買紅和藍各至少一張，已經不可能 —— 這就是剪枝。 主軸要選取值最少、限制最緊的那個（這裡金 $8$ 點最貴，只能買 $1\sim4$ 張），情況最少。

分類討論：切成互斥又窮盡的類別

當情況天然分成幾種「型態」時，就分類處理。好的分類要同時滿足兩個條件：

• 互斥（不重疊）：任一情況只落在一類，才不會重複算。
• 窮盡（無遺漏）：所有情況都被某一類涵蓋，才不會漏。

例：兩位數、十位 $<$ 個位、兩數字乘積為偶。依「個位的奇偶」分類，兩類自然互斥又窮盡：

兩位數，十位 $<$ 個位，且兩數字乘積為偶

1. 個位是偶數

   乘積必為偶，十位不受限，只要 $1 \le$ 十位 $<$ 個位。個位取 $2,4,6,8$ 時，十位分別有 $1,3,5,7$ 種。

   16 種

2. 個位是奇數

   個位是奇數 → 十位必須是偶數乘積才會偶。個位取 $3,5,7,9$ 時，十位分別有 $1,2,3,4$ 種。

   10 種

換個切法（依「有沒有含 $0$」）也可以，只要一樣互斥且窮盡，答案不變 —— 這正是好分類的檢驗方式。

保證不重不漏的三個習慣

• 強加順序（有序化）：要選一組數卻不看順序時，規定 $a<b<c$（或 $a\le b\le c$），一次只數「由小到大」那一種排法，天然去除重複。
• 字典序推進：像查字典一樣一位一位定，定完高位再定低位，走過就不回頭。
• 邊做邊剪枝：用題目限制（範圍、總和、倍數）先卡掉不可能的分支，縮小要窮舉的量。例：三數和固定，定了前兩個，第三個就被決定，只需檢查它是否合法。

常見陷阱（很多人在這裡掉分）

• 分類不互斥 → 重複計數：兩類有交集卻各數一次，把重疊算兩遍（這時要嘛改分類、要嘛用容斥扣回）。
• 分類不窮盡 → 漏情況：忘了某個邊界型態（如「等於」、「$0$」、空的情形）。
• 有序 vs 無序混用：一下把 $(a,b)$ 當有序、一下當無序，答案會差一個倍數。先講清楚「順序算不算」。
• 主軸選錯：拿取值最多的變數當主軸，情況爆炸、又容易數錯；改挑限制最緊的。
• 忘了套限制剪枝：把所有組合都列出來才篩，既慢又易漏；限制要在列舉時就用上。
• 邊界沒檢查：$\le$／$<$、含不含端點、「至少」「不超過」——每個字都要精準翻成條件。

和其他技巧的關係

• 列到後面發現「其實在數某方程的整數解」，就接 整數解與不定方程。
• 分類出現重疊、要扣重複時，用 容斥原理。
• 系統列舉常是驗證組合公式對不對的「土法煉鋼」後盾——小情況先手數，再對照公式。

學完動手

選主軸、切互斥類、強加順序去重——這套「有章法地窮舉」要靠多做幾題才練得穩。到練習題庫做本知識點的原創分層練習，每題附完整繁中詳解。