HDU4388-Stone Game II-Nim變形
//acm.hdu.edu.cn/showproblem.php?pid=4388
Nim變形，對一個\(n\)個石子的堆，每次操作從一堆中取\(k(0<k<n)\)個（注意不能全取光），同時要保證\(n\oplus k<n\)，並添加一堆新的大小為\(n\oplus k\)的石子。
同時每個人在整個遊戲中還各自有一次機會把添加的大小為\(n\oplus k\)的石子改為\(n\oplus (2k)\)個石子，同樣是不能操作的輸，兩個人採取最優策略。
初步想法
一般性地，我們還是先不管\(n\oplus k\)變成\(n\oplus(2k)\)這個操作，先想清楚沒有這種操作的情況
很自然地去手算幾個小數據，以及往二進制的方向想（畢竟異或都出來了），\(n=1,2\)都直接不能操作，\(n=3=(11)_2\)的時候可以取一個\(k=1\)或者\(k=2\)，接下來\(k=4=(100)_2\)又不能操作了…
仔細想想就會發現對於一個\(2^k=(\underbrace{100\dots00}_{k個0})_2\)不管怎麼取一個比\(n\)小的\(k\)，異或之後一定比\(n\)大，所以對於一堆的\(2^k\)就是一個不能操作的狀態。同樣如果是\((100\dots 010\dots 00)_2\)這樣的東西，只要取一個\(k=(100\dots000\dots00),n\oplus k=(000\dots010\dots00)_2\)一定是滿足條件的。
（也就是從\(n\)的1裏面選一些1出來當\(k\)，剩下\(n\oplus k\)一定是小於\(n\)的）
於是有了初步的想法，二進制表示下\(m\)個1的\(n\)至少可以按照這種拆法拆\(m-1\)次
進一步如果這麼拆，當\(m\)是奇數時先手必敗，否則必勝
進一步
不過仔細想想好像也不一定要那麼拆，比如：
\]
5位→2位+5位，4次→1次+4次=5次，嗯？乍一看好像上面那樣優雅的結論被破壞掉了…（當時推到這裡差點放棄前面的思路…）冷靜想一想，一次操作改變奇偶性…這不還是很河裡嘛…（先手奇→留給後手偶）
而且雖然1的個數變多了，但是其實在兩個人都採取最優策略的情況下具有必勝策略的那個人其實每次單獨拿一個\(2^k\)出來就總是能把1的個數降下來…所以終究是能把遊戲結束掉
證明一下？
似乎不管怎麼拆，每次拆完都會改變奇偶性。怎麼證呢…
- 考慮某一位\(p\)，如果\(n\)的這一位為1，\(p\)的為0，那麼\(n\oplus k\)的結果是1
- 類似地，列出四種情況，奇偶性一定不變
為什麼呢…好像很顯然…因為異或本來就是模二意義下的加法…奇偶性當然不變了…
證明了個寂寞
於是有結論：\(n\)中1的個數和\(k\)與\(n\oplus k\)中1的個數之和的奇偶性相同
好像快做完了
這麼看來好像\(n\oplus k\to n\oplus (2k)\)就是純粹拿來唬人的呀…畢竟奇偶性還是不變（因為\(k\)和\(2k\)中的1的個數是一樣的，再套用上面的結論）
甚至能再引進一個\(p,q\)表示兩個人能把\(n \oplus k\to n\oplus (2k)\)的次數拿來嚇人（
於是就愉快地做完了
根據初始狀態算出來「能進行操作的次數」，判一下奇偶性
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int N=1e5+5;
int f[N];
inline int calc(int x)
{
if(f[x])return f[x];
int r=0;
while(x){if(x&1)r++;x>>=1;}
return f[x]=r;
}
int main()
{
int T;scanf("%d",&T);
rep(tc,1,T)
{
int n,r=0;
scanf("%d",&n);
rep(i,1,n)
{
int a;scanf("%d",&a);
r+=calc(a)-1;
}
printf("Case %d: ",tc);
if(r&1)printf("Yes\n");
else printf("No\n");
}
}
