一类SG函数递推性质的深入分析——2018ACM陕西邀请赛H题
題目描述
定義一種有根二叉樹\(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: ROS Indigo下安装测试Xtion
- 下一篇: LeetCode——15. 3Sum