題目描述

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

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

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

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

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

樣例：

1 2 5

1 2 10

輸出：

1

17

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

解題思路

SG函數(shù)的求解

該問題等價于不能拿掉總的根，無法操作者輸。關(guān)于該問題顯然應(yīng)從SG理論入手。下面推導(dǎo)一般樹意義下的SG函數(shù)。

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

證明：利用數(shù)學(xué)歸納法，對樹的結(jié)點進(jìn)行歸納。

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

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

證畢。

引理2：設(shè)樹\(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\)的游戲之和，之間互不影響，因為不到最后一步任何人不會拿掉總的樹根。根據(jù)引理1即得上式。

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

轉(zhuǎn)化為動態(tài)規(guī)劃問題

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

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

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

轉(zhuǎn)移：對于\(i>2\)的情形，必然從其中一棵子樹中選擇拿掉一棵子樹。以拿掉左子樹中的一棵子樹為例：此時右子樹SG值不變，為了使之后原樹SG變?yōu)閈(j-1\)，必須使左子樹SG值變?yōu)閈(((j-1)\oplus (SG[i-1]+1))-1\)。特別地，當(dāng)\((j-1)\oplus (SG[i-1]+1)\)為0時，表示必須拿掉左子樹。這樣可得轉(zhuǎn)移方程： \[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]\)。這樣我們便在狀態(tài)數(shù)的時間復(fù)雜度內(nèi)解決了本問題。

狀態(tài)數(shù)的分析

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

關(guān)于異或遞推式

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

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

證明：由于\(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\]

那么根據(jù)遞推式必有（對任意\(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\)是循環(huán)節(jié)。證畢。

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

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

情況1：001001......循環(huán)節(jié)為3；

情況2：010010......循環(huán)節(jié)為3；

情況3：100100......循環(huán)節(jié)為3；

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

定理5：當(dāng)\(a[i] \mod 2\)的循環(huán)節(jié)為3時，\(a[i] \mod 2^k\)的循環(huán)節(jié)為\(3 \times 2^{k-1}\)。

證明：對\(k\)應(yīng)用數(shù)學(xué)歸納法，關(guān)鍵在于考慮低\(k-1\)位向高位的進(jìn)位。設(shè)想若低\(k-1\)位不進(jìn)位，第\(k\)位循環(huán)節(jié)必然是1或3（類似引理4）；只有低位進(jìn)位才會打亂高位的循環(huán)節(jié)。

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

0232210（進(jìn)位）23221……循環(huán)節(jié)為6，中間有1次進(jìn)位；

00120（進(jìn)位）30（進(jìn)位）0（進(jìn)位）120（進(jìn)位）3 ……循環(huán)節(jié)為6，中間有3次進(jìn)位，且其中兩次進(jìn)位的位置模3余數(shù)相同；

歸納：設(shè)\(a[x]_k\)表示\(a[x]\)第\(k\)位?？紤]在位置\(x\)低\(k-1\)位向第\(k\)位有一次進(jìn)位。這將導(dǎo)致\(a[x]_k\)取反，進(jìn)一步導(dǎo)致\(a[x+1]_k\)取反，\(a[x+2]_k\)不變，這種取反是3個一循環(huán)的。

直到低\(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\)位必然不同。進(jìn)一步地，設(shè)\(x \mod 3=i\)，則對于所有\(zhòng)(j\)，\(a[3j+i]\)和\(a[3j+i+3 \times 2^{k-2}]\)第\(k\)位必然不同。

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

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

根據(jù)證明過程立即可得推論6：

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

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

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

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

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

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

總結(jié)

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

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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbh2047/p/9076931.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。