【hdu1536】【poj2960】S-Nim
题意
题意就是给出一个数组h，为每次可以取石子的数目。
然后给你n堆石子每堆si。求解先手能不能赢？
分析
根据\(h\)数组预处理出\(sg[i]\)表示\(i\)个石子对应的\(sg\)值。
然后\(sg[s_1]\otimes sg[s_2]\otimes ...\otimes sg[s_n]\)即可。
小结
SG函数的使用，通常是ICG模型上不只存在一个石子。
如果只存在一个，可以简化SG函数，直接用布尔值代替。这样的普适性虽然没这么高，但是可以降低运算复杂度。
【hdu1848】Fibonacci again and again
题意
题意：取石子问题，一共有3堆石子，每次只能取斐波那契数个石子，先取完石子者胜利，问先手胜还是后手胜
\(n,m,p\leq 1000\)
分析
预处理斐波那契数。
求sg值。
【hdu1847】Good Luck in CET-4 Everybody!
题意
1、 总共n张牌;
2、 双方轮流抓牌；
3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
分析1
计算SG函数。
sg[0]=0;
rep(i,1,U_N) {
for (int j=1;j<=i;j<<=1)
mrk[sg[i-j]]=i;
rep(j,0,i+1)
if (mrk[j]!=i) {
sg[i]=j;
break;
}
}分析2
其实分析1过于复杂了。
根本不用求出SG函数的值，因为我们只有单一的石子在移动。
我们只用算出SG值对应的布尔值即可。
rep(i,1,U_N) {
for (int j=1;j<=i;j<<=1)
if (!sg[i-j]) {
sg[i]=1;
break;
}
}分析3
分析2的方法可以进行记忆化搜索。
这就是所谓的对抗搜索。
分析4
由于涉及到了2的幂，这看似有进一步的规律可循。
直接打表，进一步的找SG函数的规律，化简运算复杂度。
发现呈现110110110110......的规律。
直接OK了。
while (~scanf("%d",&n)) {
if (n%3!=0)
printf("Kiki\n");
else printf("Cici\n");
}小结
（1）博弈问题的思路：
①找规律
②对抗搜索 or 递推
③SG函数
从上到下由简到繁。
（2）注意SG的值的上下界。
SG的取值或许有一个较小的上界。
SG的取值总长均摊下来或许比想象中优。
对于一般的情况，有\(sg[i]<i的度数\)
对于线性的情况，必定有\(sg[i]<i\)
【hdu3032】Nim or not Nim?
题意
每一轮从两种操作中做一种：
①取走任意个石子
②分成两堆
\(每堆石子数\leq 10^9\)
分析
首先求出\(sg\)。
\(sg[n]=mex(sg[0],sg[1],...,sg[n-1],sg[0]\otimes sg[n],sg[1]\otimes sg[n-1],sg[2]\otimes sg[n-2],...,sg[n]\otimes sg[0])\)
直接求解\(O(n^2)\)，不行，所以必然找规律化简。
发现：
int SG(int x) {
if (x%4==1) return x;
else if (x%4==2) return x;
else if (x%4==3) return x+1;
else if (x%4==0) return x-1;
}核心代码
int cas;
int n;
int xorSum;
int SG(int x) {
if (x%4==1) return x;
else if (x%4==2) return x;
else if (x%4==3) return x+1;
else if (x%4==0) return x-1;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("xsy1159.in","r",stdin);
freopen("xsy1159.out","w",stdout);
#endif
cas=rd();
rep(tms,1,cas) {
n=rd(); xorSum=0;
rep(i,1,n) xorSum^=SG(rd());
if (xorSum>0) printf("Alice\n"); else printf("Bob\n");
}
return 0;
} 小结
（1）做这道题的时候第一次错了，因为暴力求SG写错了。
所以这启示我不论什么程序都要好好写，就算没有好好写都要检查一遍。
（2）一个状态的集合也可以当做一个单点的SG。
【xsy1159】【gzoi2015】石子游戏
题意
Alice 和 Bob 总喜欢聚在一起玩游戏（T_T），今天他（她）们玩的是一款新型的取石子游戏。游戏一开始有 N 堆石子，Alice 和 Bob 轮流取出石子。在每次操作中，游戏者必须选择其中的一堆石子，并作出下列的其中一种操作：
(1)移去整堆石子
(2)假设石子堆中有 X 颗石子，取出 Y 颗石子，其中 1≤Y<X ，且 gcd(X,Y)=1
游戏结束的条件是：取出最后一颗石子的人胜出。众所周知，Alice和Bob都是绝顶聪明的，假设他们在游戏中都采取最优的策略，问最后谁会胜出游戏呢？
\(T,N\leq 100\)
\(石子个数\leq 10^6\)
分析
【定义1】
若\(n=1\)，则\(s_n=1\)
若\(n>1\)，则\(s_n=mex_{1\leq i\leq n且(i,n)=1}(s_i)\)
【定义2】
函数\(r\)是\(Z\)到\(Z\)的一个映射，即\(r:Z\rightarrow Z\)，\(r(n)\)表示比\(n\)小的素数个数。
例如：\(r(2)=1,r(3)=2,r(5)=3\)
【定义3】
\(m(n)\)：\(n\)的最小正因子
例如：\(m(2)=2,m(15)=3,m(16)=2,m(56)=7\)
【定理1（\(s_n\)的封闭形式）】
对于任意整数\(n\)，\(n>1\)，\(s_n=s_{m(n)}=r(m(n))+1\)
证明：（1）当\(n=1\)时，\(r(m(n))=r(1)+1=1\)，\(s_1=1\)
\(\therefore s_1=r(m(1))+1\)
（2）假设当\(n<k\)时都成立，求证当\(n=k\)时亦成立
①当\(k\)为素数时，
\(s_k=mex(s_1,s_2,...,s_{k-1})=r(k)+1\)
②当\(k\)为合数时，
要证：\(s_k=r(m(k))+1\Leftrightarrow mex_{1\leq i<k且(i,k)=1}(s_i)=r(m(k))+1\)
即证：满足以下两个条件
A. \(\forall x\in[1,r(m(k))],\exists i\in[1,k)且(i,k)=1,s.t.s_i=x\)
B. \(\not\exists i\in [1,k)且(i,k)=1,s.t.s_i=r(m(k))+1\)
条件A证明：取1和比\(m(k)\)小的素数即可一一构造出来
条件B证明：\(s_i=r(m(i))+1=r(m(k))+1\)
即要使得\(m(i)=m(k)\)
而\(i\)与\(k\)互质，所以一定不存在。
综上，对于任意整数\(n\)，\(n>1\)，\(s_n=s_{m(n)}=r(m(n))+1\)
证毕！
上面摆了整个证明的过程。
那么，思考的过程应该是怎么样的？怎么才能推出这样的答案呢？
首先，最基本的，我列出了\(s\)的\(O(n\log n)\)递推一位的关系式。
接下来，需要考虑的就是怎么优化了，即怎么找规律。
嗯，由于这道题涉及了gcd，所以规律应该会和素数、质因数分解一类的有些关系，就让我写个暴力的程序，先找找素数的规律。
发现了\(s_k=r(k)+1\)。
那么，对于合数，又有怎样的规律呢？
由于数据范围比较大，我想到了线性筛，所以要在线性筛的过程中求解sg函数吗。
所以应该会和最小质因子有关系，发现和最小质因子的值直接相同了！
规律寻找完毕！！
小结
那么，这道题目给了我怎么的启发呢？
像这样一道题，它明显地摆着是要找规律了。那我就先根据一些特性猜测一下规律，写个程序或者手算小数据看看。
核心代码
void init(void)
{
sg[1]=v[1]=used[1]=1,tt=2;
for (int i=2;i<M;i++)
{
if (!v[i])
{
p[++p[0]]=i;
sg[i]=p[0]+1;
for (;used[tt];tt++);
pre[p[0]]=tt;
}
for (int j=1;j<=p[0];j++)
{
if (i*p[j]>=M) break;
v[i*p[j]]=1,sg[i*p[j]]=pre[j];
if (i%p[j]==0) break;
}
used[sg[i]]++;
}
}