題目描述

定義一種有根二叉樹\(T(n)\)如下：

（1）\(T(1)\)是一條長度為\(p\)的鏈；

（2）\(T(2)\)是一條長度為\(q\)的鏈；

（3）\(T(i)\)是一棵二叉樹，它的左子樹是\(T(i-2)\)，右子樹是\(T(i-1)\)。

現在給定\(p,q,n\)，現在Alice和Bob在樹\(T(n)\)上玩游戲，每人輪流從樹上拿掉一棵子樹，直到有一個玩家拿掉根結點所在的子樹為止（那么該玩家輸了）。現在問先手在第一輪有多少種拿掉子樹的方法，可以保證之后自己一定能贏。只用輸出答案最后18位即可。

樣例：

1 2 5

1 2 10

輸出：

1

17

數據范圍：保證\(n,p,q \le 2000\)。

解題思路

SG函數的求解

該問題等價于不能拿掉總的根，無法操作者輸。關于該問題顯然應從SG理論入手。下面推導一般樹意義下的SG函數。

引理1：設樹\(T\)只有一個兒子，即具有子樹\(T_1\)，則\(SG(T)=SG(T_1)+1\)。

證明：利用數學歸納法，對樹的結點進行歸納。

初始：當\(T\)只有2個結點時，顯然成立。

歸納：設\(take(T)\)為\(T\)去掉一棵子樹后所有可能的樹形態的集合。根據SG基本定理， \[SG(T)=mex(\{T' \in take(T):SG(T')\})\] 利用歸納性質， \[SG(T)=mex(\{0\} \cup \{T' \in take(T_1):SG(T')+1\})=SG(T_1)+1\]

證畢。

引理2：設樹\(T\)具有子樹\(T_1,\cdots,T_k\)，則\(SG(T)=\mathop? \oplus \limits_{1 \le j \le k} (SG({T_j}) + 1)\)。

證明：對于樹\(T\)的游戲，顯然等價于只有子樹\(T_1,\cdots,T_k\)的游戲之和，之間互不影響，因為不到最后一步任何人不會拿掉總的樹根。根據引理1即得上式。

根據以上引理，本題中便可得出\(SG[i]=(SG[i-1]+1)\oplus (SG[i-2]+1)\)，即可在\(O(n)\)時間復雜度求出原問題中每個\(T(i)(i\le n)\)的SG值。

轉化為動態規劃問題

如果原問題問誰贏那么就已經做完了。然而現在問的是第一個人第一步有幾種能贏的方案，也就是說有幾種拿走子樹的方案使得之后SG為0。

考慮動態規劃。設\(dp[i][j]\)表示在樹\(T(i)\)上玩游戲，先手拿走一棵子樹后SG值變為\(j-1\)的方案數（這里\(j-1\)是為了后續方便），\(dp[i][0]\)恒定義為1。

初始化：對任意\(1\le j < p\)，\(dp[1][j]=1\)；對任意\(1\le j < q\)，\(dp[2][j]=1\)；

轉移：對于\(i>2\)的情形，必然從其中一棵子樹中選擇拿掉一棵子樹。以拿掉左子樹中的一棵子樹為例：此時右子樹SG值不變，為了使之后原樹SG變為\(j-1\)，必須使左子樹SG值變為\(((j-1)\oplus (SG[i-1]+1))-1\)。特別地，當\((j-1)\oplus (SG[i-1]+1)\)為0時，表示必須拿掉左子樹。這樣可得轉移方程： \[dp[i][j]=dp[i-2][(j-1)\oplus (SG[i-1]+1)]+dp[i-1][(j-1)\oplus (SG[i-2]+1)]\] 最終答案為\(dp[n][1]\)。這樣我們便在狀態數的時間復雜度內解決了本問題。

狀態數的分析

問題關鍵在于確定\(dp[i][j]\)中\(j\)到底需要計算到多少。考慮所有\(SG[i](i \le n)\)中二進制位數的最大值（設為\(k\)），那么只需計算\(j < 2^k\)即可。這是因為只要\(j < 2^k\)，則轉移過程中的\((j+1) \oplus SG[i-1]]\)以及\((j+1) \oplus SG[i-2]\)也必然小于\(?2^k\)。所以現在關鍵問題在于計算\(SG[i](i \le n)\)中二進制位數的最大值到底是多少。事實上，推導這一問題較為復雜，將留在下一節專門討論，同時將會得到許多有用的性質。（PS：賽場上我大力猜了一波\(SG[i]<2^{13}=8192\)，然后就AC了2333）

關于異或遞推式

以下以本題中所用遞推式為例（令\(a[i]=SG[i]+1\)變形為\(a[i]=(a[i-1]\oplus a[i-2])+1\)），討論異或遞推式的奇妙性質。

引理3：對任意正整數\(k\)，\(a[i] \mod 2^k\)具有循環節。

證明：由于\(a[i] \mod 2^k\)只有有限種取值，故必存在\(x<y\)，使得

\[a[x]?\equiv a[y] \mod 2^k,a[x+1]?\equiv a[y+1] \mod 2^k\]

那么根據遞推式必有（對任意\(z>0\)）

\[a[x+z]?\equiv a[y+z] \mod 2^k\]

另一方面，\(a[i-2]=a[i-1]\oplus (a[i]-1)\)，故上式對\(z<0\)也成立。

故\(y-x\)是循環節。證畢。

引理4：\(a[i] \mod 2\)的循環節必為1或3，且循環節為1時數列是有界的。

證明：只需按a[1]和a[2]的值枚舉即可：

情況1：001001......循環節為3；

情況2：010010......循環節為3；

情況3：100100......循環節為3；

情況4：1111111......循環節為1，此時遞推式中的+1永遠不進位，而\(a[4]\)的高位\(=a[3]\)的高位異或\(a[2]\)的高位\(=(a[2]\)的高位異或\(a[1]\)的高位\()\)異或\(a[2]\)的高位\(=a[1]\)的高位，故最終推出\(a[i]=a[i \mod 3]\)。證畢。

定理5：當\(a[i] \mod 2\)的循環節為3時，\(a[i] \mod 2^k\)的循環節為\(3 \times 2^{k-1}\)。

證明：對\(k\)應用數學歸納法，關鍵在于考慮低\(k-1\)位向高位的進位。設想若低\(k-1\)位不進位，第\(k\)位循環節必然是1或3（類似引理4）；只有低位進位才會打亂高位的循環節。

基礎：\(k=2\)時，通過枚舉\(a[1],a[2]\)模4的余數取值可得所有情況，事實上只有2種：

0232210（進位）23221……循環節為6，中間有1次進位；

00120（進位）30（進位）0（進位）120（進位）3 ……循環節為6，中間有3次進位，且其中兩次進位的位置模3余數相同；

歸納：設\(a[x]_k\)表示\(a[x]\)第\(k\)位。考慮在位置\(x\)低\(k-1\)位向第\(k\)位有一次進位。這將導致\(a[x]_k\)取反，進一步導致\(a[x+1]_k\)取反，\(a[x+2]_k\)不變，這種取反是3個一循環的。

直到低\(k-1\)位的下一周期，\(a[x+3 \times 2^{k-2}]_k\)再次被取反從而不變了，之后\(a[x+1+3 \times 2^{k-2}]_k\)也不變……這樣一來，\(a[x]\)和\(a[x+3 \times 2^{k-2}]\)第\(k\)位必然不同。進一步地，設\(x \mod 3=i\)，則對于所有\(j\)，\(a[3j+i]\)和\(a[3j+i+3 \times 2^{k-2}]\)第\(k\)位必然不同。

對于基礎里的兩種情況，無論是有一次進位，還是有3次進位但兩次位置模3余數相同（從而抵消了），均可以保證\(a[3j+i]_k \neq a[3j+i+3 \times 2^{k-2}]_k\)。從而\(a[i] \mod 2^k\)的循環節為\(3 \times 2^{k-1}\)。

接下來再得到第\(k\)位向\(k+1\)位一個循環內的進位情況。由于對于位置\(x\)和\(x+3 \times 2^{k-2}\)低\(k-1\)位向第\(k\)位分別有一次進位，而\(a[x]_k\)和\(a[x+3 \times 2^{k-2}]_k\)又不同，故必有且僅有一次使得低\(k\)位向第\(k+1\)位進位。因此在一個周期\(3 \times 2^{k-1}\)內，一共向第\(k+1\)位的進位次數仍滿足基礎中的兩種情況（進位1次或進位3次但有兩次位置模3余數相同）。歸納證畢。

根據證明過程立即可得推論6：

推論6：低\(k\)位在一個周期內最多向第\(k+1\)位進位3次。

定理7：\(a[n]=O(\max(n,p,q))\)。

證明：設\(k\)是最小的滿足\(n < 3 \times 2^k\)且\(p,q \le 2^{k+1}\)的正整數。那么在前\(3 \times 2^k\)個數中，低\(k+1\)位最多進位3次。因此\(a[i] < 2^{k+4}\)。

將\(k\)用\(n,p,q\)表達得\(2^k \le \max(p,q,2n/3)\)，因此\(a[i] < 16\max(p,q,2n/3)\)。證畢。

定理7表明了本題所使用算法的時間復雜度為\(O(n \times \max(n,p,q))\)。（然而我不清楚出題人是否也是這么證明的（或者并沒有證明直接默認了），如果有更簡單的方法請務必聯系我！）

PS：感謝Emil Je?ábek對以上的證明提供了巨大的幫助！

總結

在SG理論中，通過打表找出SG的規律是一類常見的題型，然而很多時候證明SG的規律是較為困難的。本文以\(a[i]=(a[i-1]\oplus a[i-2])+1\)為例詳細推倒了周期性、上界等結論，這種結論實際上是很有一般性的。許多題目中SG函數均存在異或遞推式，從而具有類似的周期性。然而應用SG的上界作為狀態進行DP的題目則十分具有創新意義，希望以后可以出現更多的以博弈作為橋梁考察異或性質的題目。

AC代碼

1 #include<cstdio> 2 #include<cstring> 3 const long long mod = 1e18; 4 int sg_1[2001]; 5 long long dp[2001][8192]; 6 int main() 7 { 8 int n, p, q; 9 while (scanf("%d%d%d", &p, &q, &n) == 3){ 10 sg_1[1] = p; sg_1[2] = q; 11 for (int i = 3; i <= n; i++) 12 sg_1[i] = (sg_1[i - 2] ^ sg_1[i - 1]) + 1; 13 memset(dp[1], 0, sizeof(dp[1])); 14 memset(dp[2], 0, sizeof(dp[2])); 15 for (int i = 0; i < p; i++) 16 dp[1][i] = 1; 17 for (int i = 0; i < q; i++) 18 dp[2][i] = 1; 19 for (int i = 3; i <= n; i++){ 20 dp[i][0] = 1; 21 for (int j = 1; j < 8192; j++) 22 dp[i][j] = (dp[i - 1][(j - 1) ^ sg_1[i - 2]] + dp[i - 2][(j - 1) ^ sg_1[i - 1]]) % mod; 23 } 24 printf("%lld\n", dp[n][1]); 25 } 26 }

?

轉載于:https://www.cnblogs.com/zbh2047/p/9076931.html

總結

以上是生活随笔為你收集整理的一类SG函数递推性质的深入分析——2018ACM陕西邀请赛H题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。