博弈论详解 3（SG定理的运用）

时隔一年半，主播再次回到博弈论。这次是练习时间！！！

如果你没有学过SG定理或者想要复习一下

如果没有看过之前的前置文章的可以先看零基础知识讲解。
Episode 1（Nim基础）：https://blog.csdn.net/2401_84512298/article/details/141559570?spm=1001.2014.3001.5502
Episode 2（SG定理）：https://blog.csdn.net/2401_84512298/article/details/141563982
为了和我一样没有买会员的小伙伴，我把之前的文章设成公开了。

简单复盘

每个状态都有一个 SG 函数值，比如在基本的取石子问题中，一堆有x xx个石子就是一种状态。没有石子（零个）的 SG 值就是0 00（即必输的局面）。求的方法是通过状态的转移方式建立出一个以状态为节点，转移为单向边的 DAG。比如5 55个石子就可以取掉两个，转移到3 33个石子，所以5 55到3 33有一条单向边。当石子变成n nn堆的时候，就取每一堆的初始状态的 SG 函数值，然后把它们x o r xorxor一下，如果是0 00就必输，否则先手胜。

例题（先自己做做看）

原题：Codeforces 2004E
A 和 B 面前有n nn堆石子，第i ii堆有a i a_iai​个。每次可以从x xx个石子的一堆里面拿走y yy个，需满足g c d ( x , y ) = 1 gcd(x,y)=1gcd(x,y)=1。 当然你不能把石子取成负数。如果到某个人的时候他没办法取石子了，他就输了。
这里a i ≤ 10 7 , n ≤ 3 ⋅ 10 5 a_i\le 10^7, \, n\le 3\,·10^5ai​≤107,n≤3⋅105。

思路

这里的状态和复盘中的状态一模一样，都是这一堆还有几个石子。但是转移不一样了，这次每次可以取走一些特定数字的石子，但仍然是一张有向无环图。只要算出所有状态的 SG 函数，取一下初始的n nn堆所对应的函数值的x o r xorxor就搞定了。可是如果暴力算出每种石子数的 SG 值，那就 TLE 了，因为第一层循环枚举当前在求的状态（10 7 10^7107），第二层循环枚举所有小于当前石子数的值 （10 7 10^7107），也就是要取的数量。但是我们二话不说，直接开干，看看 SG 值长什么样子再说。
（这里建议读者自己写一下程序找找规律）

#include<bits/stdc++.h>#pragmaGCCoptimize("O3,unroll-loops")#pragmaGCCtarget("avx2,bmi,bmi2,lzcnt,popcnt")usingnamespacestd;#definelllonglong#defineendl'\n'll sg[205];boolhave[1005];intmain(){ios::sync_with_stdio(0);cin.tie(0);sg[0]=0;cout<<0<<':'<<sg[0]<<endl;for(inti=1;i<=200;i++){memset(have,0,sizeof(have));for(intj=1;j<=i;j++)if(__gcd(j,i)==1)have[sg[i-j]]=1;for(intj=0;j<=1000;j++)if(!have[j]){sg[i]=j;break;}cout<<i<<':'<<sg[i]<<endl;}return0;}

然后我们的输出长这样：（冒号左边为石子数，右边为所对应的 SG 函数值）

读者此时发现：我的天哪！为什么石子个数是偶数（蓝色）的都是0 00，然后那些质数（橙红色）感觉就像是编号一样，一个一个往上加？（1 11不是质数，只是加上之后才是从1 11开始加，比较好看，它刚好顶替了2 22的位置，2 22虽然是质数，但也是偶数，所以变成0 00了）更惊喜的是，主播并不知道为什么。
剩下的规律实在有点难，所以主播偷偷去看了一下题解，然后发现居然就是它的最小质因子的 SG 值。比如25 2525就取5 55的数值，3 33；77 7777就取7 77的值，4 44。那就很简单了，直接筛选一下质数，然后把 SG 值全算出来就好了。

代码

#include<bits/stdc++.h>#pragmaGCCoptimize("O3,unroll-loops")#pragmaGCCtarget("avx2,bmi,bmi2,lzcnt,popcnt")usingnamespacestd;#definelllonglong#defineendl'\n'intt,n,a[300005],sg[10000005],id,fac[10000005];boolnp[10000005];intmain(){ios::sync_with_stdio(0);cin.tie(0);memset(fac,0x3f,sizeof(fac));sg[1]=1;id=1;for(intj=2*2;j<=10000000;j+=2)np[j]=1,fac[j]=min(fac[j],2);for(inti=3;i<=10000000;i++){if(!np[i]){sg[i]=++id;for(intj=i*2;j<=10000000;j+=i)np[j]=1,fac[j]=min(fac[j],i);}}for(inti=3;i<=10000000;i+=2)if(np[i])sg[i]=sg[fac[i]];cin>>t;while(t--){cin>>n;intsum=0;for(inti=1;i<=n;i++){cin>>a[i];sum^=sg[a[i]];}if(sum==0)cout<<"Bob\n";elsecout<<"Alice\n";}return0;}

习题

https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game/problem
英文题解在评论区提供的 USACO Guide 的讲解当中，如果各位想要我写这道题的题解就发评论里，尽量更新。