SG函數(shù)

有向圖游戲及SG函數(shù)

每一個公平 ICG 游戲顯然都對應一個有向圖，把每個節(jié)點看成游戲的每個狀態(tài)，連邊代表進入下一個狀態(tài)。于是有，

有向圖游戲必敗，當且僅當目前局面 \(\mathrm{SG}>0\)。反之則為必敗。

打表的時候 \(\mathrm{SG}\) 的集合并可以用 bitset 來快速操作，取 \(\mathrm{mex}\) 就直接掃描即可。

有向圖游戲的和

有 \(m\) 個有向圖，每次可以在其中一個圖上操作一次。

總的 \(\mathrm{SG}\) 值為各個子游戲 \(\mathrm{SG}\) 函數(shù)值的異或。證明方法類似 NIM 博弈。

如果是每次可以在任意多 \((>0)\) 個游戲上操作的話就是 \(\mathrm{SG}\) 函數(shù)的或。

同樣，我們也可以知道其實 NIM 游戲中每一個單獨的堆中的 \(\mathrm{SG}\) 函數(shù)就是堆中石子個數(shù)。數(shù)學歸納法可證，首先 \(\mathrm{SG}(0)=0\)，\(k\) 節(jié)點下面有 \(k\) 個節(jié)點，\([0,k-1]\)，每一個節(jié)點的 \(\mathrm{SG}\) 值都等于石子個數(shù)，取一下 \(\mathrm{mex}\)，\(\mathrm{SG}(k)=k\)。

什么時候拆成多個有向圖？就是我們發(fā)現(xiàn)博弈中的每一個狀態(tài)形如 \((s_1,s_2,s_3...)\) 由多個狀態(tài)構成就可以拆。然后直接異或即可。

題目

AGC017D Game on Tree

一個狀態(tài)可以表示為 \((s_1,s_2,s_3....)\) 每個 \(s\) 表示 \(u\) 的一個子樹，多狀態(tài)所以這是多個有向圖。所以 \(u\) 的 \(\mathrm{SG}\) 是所有子節(jié)點 \(\mathrm{SG}\) 的異或嗎？其實不是，因為 \(v\) 到 \(u\) 還有一條邊，所以其實是子節(jié)點的 \(\mathrm{SG}\) 函數(shù)值加一再全部異或起來。可以類比 NIM 博弈。\(+1\) 的根本原因是這個是關于邊的 NIM 而不是關于點的 NIM。

P2148 [SDOI2009] E&D

如果可以算出一組石子的 \(\mathrm{SG}\) 函數(shù)，那么把他們異或起來顯然就是正確答案。

可是這個 \(\mathrm{SG}\) 函數(shù)似乎不太好直接看出來。于是我們直接打表觀察規(guī)律。

打表之后很明顯的對于二元組 \((a,b)\)，若兩者都是奇數(shù)，其 \(\mathrm{SG}\) 值為 \(0\)。這提示我們對于奇偶分類，如果兩者都是偶數(shù)的話就有 \(\mathrm{SG(a,b)}=\mathrm{SG}(\frac{a}{2},\frac{b}{2})+1\)。如果 \(a\) 偶 \(b\) 奇的話，可以通過 \(\mathrm{SG}(a,b)=\mathrm{SG}(a,b+1)\) 來轉化到兩偶的情況，這樣子可以用 $\log $ 的復雜度單點計算。

還有一種方法就是觀察相同數(shù)字法，可以分治來解決。

AT_ttpc2019_d 素數(shù)取りゲーム

列出 \(\mathrm{SG}\) 函數(shù)的轉移式子

首先有 \(SG(0)=0,SG(2)=1\)。
可以發(fā)現(xiàn) \(x-2 \notin P\) 的時候，\(SG(x)=1\)。
否則就是 \(\mathrm{SG}(x)=\mathrm{mex} \{0,1,SG(x-2)\}\)，現(xiàn)在需要對于 \(x-4\) 討論，我們可以發(fā)現(xiàn)連續(xù)三個公差為 \(2\) 的質(zhì)數(shù)只有在 \(x=7\) 的時候才能滿足（證明可以在 \(\bmod 6\) 的意義下討論一下即可），于是只要特判 \(SG(7)=3\) 即可。其余 \(SG(x)=2\)。

P6665 [清華集訓2016] Alice 和 Bob 又在玩游戲

SG 函數(shù)不方便推出什么式子，所以我們考慮直接維護。

總的 SG 函數(shù)值等于各個樹 SG 值的異或。

考慮求出一棵樹的 SG 值，假設對于一棵樹進行操作，我們要先選擇一條鏈然后去掉，剩余的就是若干個子樹，這次狀態(tài)轉移后的 SG 值就是這些子樹的異或。對于所有斷鏈方案的情況得出的 SG 值的集合并上斷根節(jié)點得到的 SG，我們?nèi)?mex 就是這顆樹的 SG 值了。

邊界：獨立點的 SG 值為 \(1\)。

考慮如果快速維護斷鏈統(tǒng)計過程，我們對于每個子樹都維護一個 SG 值的集合，包含這顆子樹所有斷鏈(從根節(jié)點開始的鏈都可以寫成：根節(jié)點+子樹的一條鏈)的 SG 值。然后每次只需要向這個集合內(nèi)異或其他子樹 SG 值的異或和即可得到斷這顆子樹內(nèi)鏈的，最后再合并到根節(jié)點(為了取 mex)。

經(jīng)典模型

NIM博弈

\(n\) 堆物品，第 \(i\) 堆有 \(A_i\) 個，兩名玩家輪流行動，每次可選某一堆中的任意多不為 \(0\) 個物品。取走最后一堆物品的人勝。

結論：先手獲勝當且僅當 \(A_1\oplus A_2\oplus...A_n \neq 0\)。
首先考慮 \(0~0~0~a\) 的情況，顯然異或值不等于 \(0\)，且先手必勝。每次先手就把當前的局面取成異或值為 \(0\) 即可，數(shù)學歸納法可證。

NIM 變型

NIM游戲 改成取完者輸。

設異或和不為 \(0\) 是 \(S\) 態(tài)，異或和為 \(0\) 是 \(T\)。

按照 \(1\) 堆的個數(shù)分為 \(S_0,S_1,S_2\)，分別表示全都是 \(1\) 堆，有 \(1\) 個非 \(1\) 堆，有多個非 \(1\) 堆。對于 \(T\) 同理分類，但是注意其實 \(T_1\) 是不可能存在的，因為若干個 \(1\) 和一個大于 \(1\) 的數(shù)不可能異或和為 \(0\)。

首先 \(T_0\) 必勝，\(S_0\) 必敗。

其次，\(S_1\) 必勝因為可以選擇將唯一一個非 \(1\) 堆拿完或者只剩一個，這樣子其中肯定有一種方式轉化為 \(S_0\)。

遇到 \(S_2\) 的時候，我們的策略就是一直轉化為 \(T\) 態(tài)就贏了，因為 \(S_2\) 只能到 \(T_2\) 態(tài)（\(T_1\) 不存在且 \(2\) 態(tài)不可能直接到 \(0\) 態(tài)）。而對面得到的 \(T_2\) 態(tài)只能到 \(S_1\) 和 \(S_2\)，如果對面選擇 \(S_1\) 我們就贏了，否則我們每次拿到 \(S_2\) 就轉化為 \(T_2\)，若干次之后石子被消耗了對面就只能選擇 \(S_1\) 態(tài)了，我們就贏了。

因此必勝態(tài)為 \(T_0,S_1,S_2\)，必敗態(tài)為 \(S_0,T_2\)。

斐波那契博弈

有一堆石子，第一次取的時候可以取走若干個（但不能取完）。之后每次至少為 \(1\) 個，至多為之前的 \(2\) 倍。取完最后一個的人勝。

當且僅當初始為斐波那契數(shù)的時候先手必敗。

巴什博弈

每次取的石子個數(shù)在 \([1,m]\)。

當 \((m+1)\mid n\) 的時候，先手必敗。

威佐夫博弈

有兩堆物品，每次從任一一堆中選取至少一個，或者從兩堆中取同樣多的物品，取光者勝。

設兩堆為 \(x,y\)，滿足 \(x>y\)，當 \(y=\lfloor\frac{\sqrt 5+1}{2}(x-y)\rfloor\) 的時候，先手必敗。

直接算可能會被卡精度，考慮轉化為上述式子在 \([b,b+1)\) 范圍內(nèi)，然后兩邊平方得解。

NIM階梯

只需要考慮奇數(shù)堆即可。異或起來按照普通 NIM 做。

P3480 [POI 2009] KAM-Pebbles

差分之后直接就是階梯博弈了

經(jīng)典題目

ARC122D XOR Game

最大/小化異或值，顯然是從高到低位貪心考慮，而不是按照博弈順序進行考慮。

其實 Bob 占據(jù)絕對主動的，也就是應該是 Bob 在游戲開始前就會想好，Alice 每次出哪個數(shù)，他就會拿哪個數(shù)來應對。

假設從高到低考慮到了第 \(z\) 位。思考什么時候這一位 Bob 可以做到 \(0\)。如果這一位有偶數(shù)個 \(1\)，那么 Bob 是可以做到為 \(1\) 的，因為所有有 \(1\) 的數(shù)可以兩兩配對。如果有奇數(shù)個 \(1\)，那么是可以做到為 \(1\) 的。

下面我們需要確定后面的位，對于第一種情況，如果 Alice 選 \(1\)，那么 Bob 選 \(1\)。如果 Alice 選 \(0\)，Bob 也應該跟著選 \(0\)。于是此時根據(jù)這一位是 \(0\) 還是 \(1\)，分裂成兩個集合，后續(xù)的操作只能在集合內(nèi)部進行，對于兩個結果應該取 \(\max\)，因為 Alice 可以選擇到 \(1\) 集合還是 \(0\) 集合。

對于第二種情況，Alice 的策略已經(jīng)確定，就是選一個當前位帶 \(1\) 的數(shù)，而且在所有一對數(shù)中也只有 Bob 選 \(0\) 才可能產(chǎn)生最終貢獻，所以 Bob 要在 \(0\) 集合中選擇一個數(shù)使得和 \(1\) 集合中的數(shù)異或的最小值最小，直接字典樹即可。

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

AGC002E Candy Piles

很巧妙的題目，博弈論題肯定是考慮狀態(tài)和狀態(tài)之間的轉移。

狀態(tài)是形如 \((a_1,a_2..a_n)\) 可以從 \((a_2,a_3..a_n)\) 和 \((a_1-1,a_2-1..a_n-1)\) 轉移而來。這樣子看起來狀態(tài)數(shù)太大了，肯定不能強行解。但是發(fā)現(xiàn)每次轉移的時候狀態(tài)的改變很小，每次的變動最多為 \(1\)，所以總的狀態(tài)數(shù)是 \(O(nV)\) 的。所以就有了暴力算法 \(O(nV)\)。

進行優(yōu)化，對于兩個前驅狀態(tài)的轉移考慮放到網(wǎng)格圖上思考。

考慮對于 \(a_i\) 降序排序然后畫成柱狀圖，然后大概就是若干個頂點坐標為 \((i,a_i)\) 的矩陣組成。可以轉化為從 \((1,1)\) 開始走網(wǎng)格。

發(fā)現(xiàn)全部都拿走一個就是往上走一步，拿走最多的就是往上走一步。如果誰從網(wǎng)格中走出去了就輸了。

由于是只有兩個相關狀態(tài)的網(wǎng)格圖所以 SG 值只有 \(0/1\)。找規(guī)律可以發(fā)現(xiàn)對角線上的 SG 值相同。

于是我們只需要找到 \(y=x\) 這條直線上最遠的點看它的 SG 值即可。

P3185 [HNOI2007] 分裂游戲

同樣是復雜狀態(tài) SG 函數(shù)題。可以發(fā)現(xiàn)狀態(tài)是 \((c_1,c_2...c_n)\)，每個狀態(tài)的后繼是 \((c_1,..,c_i-1,..c_j+1,..,c_k+1..c_n)\)，可以這么做的話狀態(tài)數(shù)太大了。思考如果簡化狀態(tài)來 SG，有一個很重要的觀察其實每個糖果是獨立的，并且如果只是添加一個的話可以看成一堆 \(n-i\) 個石子，但是本題是添加兩個。

原本單個的 SG 值就是 \(n-i\)，然后異或起來即可。那么現(xiàn)在枚舉所有轉移，\(O(n^3)\) 可以計算所有單點的 SG 值然后異或起來即可。

AGC016F Games on DAG

首先，這兩個石子可以看成兩個獨立游戲。于是根據(jù) SG 函數(shù)的結論就是當 \(\mathrm{SG}(1)\oplus \mathrm{SG}(2)=0\) 的時候，先手必敗。于是我們只要求出 \(1\) 和 \(2\) 函數(shù)值相同的方案數(shù)，然后拿總方案減去即可。

在這題中學到了 DAG 上 \(\mathrm{SG}\) 值的刻畫，就是我們考慮按照 \(\mathrm{SG}\) 值將這個圖一層層剝開。

我們設 \(\mathrm{SG}\) 值為 \(i\) 的點的集合為 \(S_i\)。對于初始的 \(S_0\)，我們要求其沒有出邊，且是一個獨立集。假設已經(jīng)確定了 \(S_0,S_1...S_{i-1}\)，新加入 \(S_i\)，我們要求其中每個點都和 \(S_0,S_1...S_{i-1}\) 有連邊，并且其是一個獨立集。

這就提供了一個很好的拆分圖的方式，我們只需要 \(1\) 和 \(2\) 在同一個 \(S_i\) 中被加入即可。

設 \(dp_{i,s}\) 表示已經(jīng)加入了 \(\mathrm{SG}\) 值為 \([0,i]\) 之內(nèi)的集合，其并集為 \(s\)，同時要求 \(1,2\) 要么沒加入，要么在上述的同一個集合內(nèi)的方案數(shù)。

在加入點的時候，統(tǒng)計邊是否要連上的方案數(shù)即可。

時間復雜度 \(O(n3^n)\)。

XYD3618 a

先觀察 W.B 的情況，可以發(fā)現(xiàn)兩邊都不能往中間地帶走了。只能把后面的兵不斷往中間靠近。如果一方不能繼續(xù)挪動后面的兵就只能一個一個將子送給對面。所以可以看出一般情況的策略就是不斷搶占中間地帶，直到雙方只隔著一個格子就碰上了，此時再挪動后面的位置。對于一般情況是很好在直接計算可移動步數(shù)來快速求解的。

但是還有一個特殊情況，就是當初局面直接就是 WB 這種直接相交的情況。如果是 WB.，那么 W 直接吃掉 B 是優(yōu)的。如果是 WBB，當 W 吃掉 B，第二個 B 必然會再吃掉 W，這個時候轉化為一般情況處理，如果這種決策會導致 W 輸，那么 W 可以選擇不吃，這個時候給 B 同理決策一下。

XYD10170.Tspin single

首先答案具有單調(diào)性可以二分答案。

判定的時候考慮根據(jù)閾值轉化為 \(01\) 序列。然后看看 Alice 能否將其留住 \(0\)。

直接貪心去取顯然是很難做的。于是我們?nèi)タ紤]什么時候 Alice 能取完 \(1\)/不能取完 \(1\)。有一個充分條件就是假設 Alice 可以操作 \(t\) 次(且最后一次是 Bob 操作)，那么我們需要劃分出 \(t\) 個長度 \(\le k\) 的區(qū)間，滿足其中 \(1\) 的個數(shù) \(\le k-1\) 且覆蓋了所有 \(1\)。猜測這個條件是充要的，也就是 Bob 可以有足夠好的策略使得每次不會減少 Alice 需要選的區(qū)間個數(shù)。

嚴謹證明我不太會，可以自己構造幾個自己覺得極端的樣例然后研究一下，還是比較能接受的結論。010100101 這個局面遇到了 \(k=3\)，此時顯然是 Alice 需要 \(2\) 次，但是 Bob 很難不做到不取原本覆蓋的 \(1\)，不過觀察到 101 這個局面兩個 \(1\) 有距離，可以從前面拉一段前綴和這個 \(1\) 組合。這樣子還剩一個 \(1\)。如果兩個 \(1\) 靠近，那么我們可以從空缺出的一側去拉一個段。

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

ABC261Ex Game on Graph

AGC056D Subset Sum Game

納什均衡

雙方博弈的時候，每個人要為自己的每種策略分配一個概率。什么情況能達到均衡呢？對于任意一個人 \(A\) 來說，求一個最大的 \(M\)，使得 \(A\) 選擇某種策略的時候，不管 \(B\) 選什么策略，\(A\) 的收益都 \(\ge M\)，那么這個時候 \(A\) 的策略就是最優(yōu)策略。

比如囚徒困境的納什均衡就是兩個人都招供。

NFLSP12569. 游戲

有 \(n\) 個房間每個房間里面有 \(a_i\) 個人在玩，你可以選擇一間房間提醒它們，老師會選擇一間房間打開去抓人，求兩個人最優(yōu)決策之下，老師期望抓到多少人？

設學生選擇 \(i\) 的概率為 \(p_i\)，老師選擇 \(i\) 的概率為 \(q_i\)。那么 \(M=\sum q_i(1-p_i)a_i\)，其中 \(\sum p_i=1,\sum q_i=1\)。

然后你會發(fā)現(xiàn)必須讓 \((1-p_i)a_i\) 盡可能均勻，否則如果老師將更大的 \(q_i\) 壓在更大的 \((1-p_i)a_i\) 上面的話，這個 \(M\) 就會變大。

所以理想情況就是所有 \((1-p_i)a_i\) 都相等，令 \(k=(1-p_i)a_i\)，然后利用 \(\sum p_i=1\) 的條件，可以算出 \(k=\dfrac{n-1}{\sum\frac{1}{a_i}}\)。

這個時候 \(M=\sum q_ik=k\)。

寫一發(fā)交上去發(fā)現(xiàn)只有 \(20\rm pts\)。

為什么呢？隨便試幾個數(shù)字，發(fā)現(xiàn)在 \(n=3\),\(a_i=1,20,4000\) 的時候答案居然 \(>1\)，可是 \((1-p_i)a_i<a_i\)，矛盾了！

其實是因為我們的 \(p_i\) 算出了負數(shù)，這個就是納什均衡的 corner case，我們要舍棄負數(shù)解。

于是我們把 \(a_i<k\) 的 \(a_i\) 都刪除繼續(xù)計算答案，不斷迭代直到滿足所有 \(a_i>k\) 為止，這意味我們的 \(p_i\in[0,1]\) 符合條件！

迭代的過程可以用二分答案替代。

P9142 [THUPC 2023 初賽] 欺詐游戲

注意到題目里的這句話

你需要保證，在一方的策略不變的情況下，另一方無論如何改變自己的策略，都不能使自己的期望收益比原來多。

不妨從檢察官的視角來看待這個問題（走私者同理）。

走私者放 \(i\) 元的收益顯然與檢察官猜某大小的概率有關。

設走私者放 \(i\) 元的收益為 \(E(i)\)。檢察官猜 \(i\) 的概率為 \(p_i\)。

那么 \(E(i)=\sum\limits_{j=0}^{i-1}i\times p_j+\sum\limits_{j=i+1}^{n}p_j\times \dfrac{j}{2}\)。

如果我們的策略中滿足 \(\{p_j\}\) 讓某個 \(E_i\) 的比較大，那么如果走私者調(diào)整策略壓到那個比較大的 \(E\) 上面就可以讓自己收益期望變大，故不符合題目條件。

所以可以得出所有 \(E\) 都是相等的。

據(jù)此可以推出 \(p\) 的表達式，對于 \(q\) 同理。

QOJ10432. Fugitive Frenzy

先考慮雙方的基本策略：

• A：從當前節(jié)點選擇一個葉子方向，一直走到那個葉子（畢竟 \(B\) 可以不斷往里面縮，你不走到葉子肯定抓不到，所以必須走到底）。

• B：以 \(A\) 走到葉子為一個回合，每個回合選擇一個葉子一直待在里面直到回合結束。（\(B\) 在此期間的任何調(diào)整都可以證明不優(yōu)于以上策略，因為調(diào)整的過程中可能被抓到，而且最終無論如何都要縮進一個葉子里）。

于是我們設一些未知數(shù)，\(f_u\) 表示起點為 \(u\) 的時候雙方最優(yōu)策略下期望多少輪會結束。\(p_{u,v}\) 表示 \(A\) 在 \(u\) 點的時候會選擇哪個 \(v\) 點（葉子）向其進發(fā)。\(q_{u,v}\) 表示 \(A\) 從 \(u\) 點出發(fā)的時候 \(B\) 會選擇哪個 \(v\) 躲在里面。

有了這些就可以列方程了，

由于 \(\sum\limits_{v} p_{u,v}=1\) 且 \(\sum\limits_{v} q_{u,v}=1\)，總和一定，我們需要分配這些數(shù)。

• 提取 \(p_{u,v}\) 的系數(shù) \(F_u(q_v)=dis(u,v)+f_v(1-q_{u,v})\)

我們希望所有的 \(F_u(q_v)\) 都相等，否則 \(p_{u,v}\) 不均等分配的時候如果大數(shù)對大數(shù)會產(chǎn)生一個很大的數(shù)，如果所有 \(q_v\) 都相等的情況下 \(p_{u,v}\) 必須平均分配，這樣子總和就會均勻。

令 \(k=dis(u,v)+f_v(1-q_{u,v})\)，再代入 \(\sum q_{u,v}=1\)，可以得到 \(k=\dfrac{\sum \frac{d_v}{f_v}+cnt-1}{\sum \frac{1}{f_v}}\)。其中 \(cnt\) 是 \(v\) 的個數(shù)。再反帶回 \(k=dis(u,v)+f_v(1-q_{u,v})\) 即可解出 \(q_{u,v}\) 的值。

• 提取 \(q_{u,v}\) 的系數(shù) \(G_u(p_v)=-f_vp_{u,v}\)

這個不需要解方程也能看出來 \(p\) 就是權為 \(\dfrac{1}{f}\) 的加權平均數(shù)。

將以上全部代入之后可以得到 \(f_u=\dfrac{cnt-1+\sum\limits_{v\in{\rm leaf},v\neq u}\dfrac{d_v}{f_v}}{\sum\limits_{v\in{\rm leaf},v\neq u}\dfrac{1}{f_v}}\)。

這個形式難以高斯消元，可以考慮令 \(f_i=1\)，然后直接迭代這個式子 \(1000\) 次即可。