AC代碼

https://codeforces.com/contest/256/submission/180561282

題意：

Furlo和Rublo玩游戲。桌子上有n堆硬幣，第i堆有ai硬幣。Furlo和Rublo輪流移動(dòng)，F(xiàn)urlo先移動(dòng)。

在一次移動(dòng)中，您可以：

1.選擇一堆硬幣，讓我們將其中當(dāng)前的硬幣數(shù)量表示為x；

2.選擇一些整數(shù)y（0?≤?y?<?x；x^1/4≤?y?≤?x^1/2） 并將這堆硬幣的數(shù)量減少到y(tǒng)。

換句話說(shuō)，在所描述的移動(dòng)之后，這堆硬幣將剩下y個(gè)硬幣。

無(wú)法移動(dòng)的玩家會(huì)失敗。

你的任務(wù)是找出，如果Furlo和Rublo都玩得很好，誰(shuí)會(huì)在給定的游戲中獲勝。

題解：

博弈論 + SG函數(shù) + 分段打表

暴力的求SG函數(shù)會(huì)超時(shí)，正解是先處理出10^5以內(nèi)的SG值，可以發(fā)現(xiàn)sg函數(shù)值成段出現(xiàn).

根據(jù)sg函數(shù)值成段出現(xiàn)的特點(diǎn)，構(gòu)造函數(shù)sg[lower_bound(a, a+6, i)-a]。

根據(jù)10^5以內(nèi)的SG值，使用該函數(shù)，容易計(jì)算全部SG值(<=777777777777)

?