← 回首頁
雜項（Nim 賽局 / Meet-in-the-Middle 子集和 / QuickSelect / Mo's 演算法）
這頁像一個裝雜物的工具箱 ，收了四個彼此不相干的聰明捷徑 ，共通點都是「不想笨笨地把每種可能全算一遍」。Nim 賽局 教你一眼看穿拿石子遊戲誰穩贏；Meet-in-the-Middle 把太多的組合拆成兩半、分頭算完再湊起來；QuickSelect 不必整排排好就能挑出第 k 名；Mo's 演算法 把一大堆查詢重新排順序，省下反覆翻找。下面每個都能一步步播放，看它怎麼偷懶得漂亮。
四個各自獨立、互不隸屬的經典技巧：
Nim 賽局 ：公平博弈（impartial game）的必勝判定——多堆物件的 XOR 和（Bouton 定理）決定先後手勝負，可據此每步找出必勝移動。Meet-in-the-Middle 子集和 ：指數複雜度的空間換時間技巧——把 O(2^n) 的子集枚舉拆成兩半各自 O(2^(n/2)) 枚舉，再排序＋二分搜尋合併。QuickSelect ：不需完整排序即可找出第 k 小／大元素的期望線性時間隨機化選擇演算法。Mo's 演算法 ：離線（查詢全部已知）多區間查詢的分塊排序技巧——重新排序查詢後用雙指標增量維護答案，避免每次重新掃描。
1. Nim 賽局（多堆 XOR 必勝策略）
每輪計算目前所有堆的 XOR 和 s：s≠0 為先手必勝局，找出最小索引 i 使 pile_i XOR s < pile_i，
從該堆取走 pile_i-(pile_i XOR s) 顆即可維持必勝；s=0 時無必勝步，決定性慣例改為從最小非空堆取走 1 顆。
重複至所有堆為 0（normal play），取走最後一顆的一方獲勝。
固定示範（同 nim.test.js NIM_PILES）：piles=[3,4,5]，XOR=3⊕4⊕5=2≠0 → 先手必勝
重播
步數：0
紅色（checking）標示本步被取走的堆；長條高度為該堆目前剩餘數量。
Nim 的必勝判定是本頁的「精確解」；蒙地卡羅樹搜尋（MCTS）反過來用大量隨機模擬去逼近這個精確解——拿 Nim
這種可窮舉的小賽局當教學縮尺，展示「估計 vs 真值」的收斂過程 →
蒙地卡羅樹搜尋 MCTS/UCB
2. Meet-in-the-Middle 子集和（折半列舉）
將陣列拆半，分別枚舉左半、右半所有子集和（各 2^(n/2) 個），把右半排序後，
對每個左半和 ls 二分搜尋 need=target-ls；找到即宣告 found=true，全部掃完仍未找到則 found=false。
固定示範（同 mitm-subset-sum.test.js MITM）：arr=[3,34,4,12,5,2]，target=9（4+5=9 存在）
重播
枚舉數：0
左欄為 leftSums、右欄為 rightSums（右半終態為排序後）；反白（active）標示目前二分搜尋的 leftSum 與對應 need。
3. QuickSelect（隨機化快速選擇，固定種子示範）
以 Lomuto 分割法選定 pivot，將小於 pivot 的元素換到左側；比較分割後的 storeIndex 與 k-1，
相等即為第 k 小，否則遞迴縮小到左半或右半繼續搜尋。
固定示範（同 quickselect.test.js QSEL）：arr=[7,10,4,3,20,15]，k=3（排序後 [3,4,7,10,15,20]，第 3 小=7）
重播
分割輪數：0
紫色（pivot）為本輪 pivot 索引；藍色（comparing）為目前比較的元素；淡出（out）為已排除的搜尋範圍外索引。
pivot 由固定種子（seed=42）LCG 決定，僅供教學示範可重播；實務隨機化 QuickSelect 應使用真隨機亂數。
QuickSelect 靠隨機 pivot 把選第 k 小的期望時間壓到 O(n)；同屬隨機化演算法家族的 Reservoir Sampling
與 Alias Method，把「隨機性」用在維持串流代表性樣本、以及依機率分佈做 O(1) 抽樣 →
取樣演算法 Reservoir/Alias
4. Mo's 演算法（離線區間相異數）
依 (L 所在塊, R, 原始索引) 排序查詢，初始化空窗 curL=0、curR=-1，逐查詢移動雙指標
（擴右→縮右→擴左→縮左）增量維護 distinct，窗口就緒時記錄該查詢的答案。
固定示範（同 mos.test.js MOS）：arr=[1,2,1,3,2,1,4,3]，queries=[[0,4],[2,7],[1,5],[4,7]]
重播
指標移動次數：0
藍色外框（range）標示目前雙指標覆蓋的窗口 [curL,curR]（初始為空窗 curR=-1）。
此處查詢排序僅依 (L 所在塊, R, 原始索引)，未含奇偶塊優化，實務可再省下指標移動次數。
各查詢答案（依原始索引，panel.answers）
（空）
Mo's 演算法用固定區塊大小把查詢分塊排序，限縮重算範圍；向量搜尋的 IVF 倒排索引也是同樣思路——
先用 k-means 把向量分塊（粗量化），查詢時只探最近幾群、避免全表暴力掃描
→
向量壓縮 PQ/IVF