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

时隔一年半主播再次回到博弈论。这次是练习时间如果你没有学过SG定理或者想要复习一下如果没有看过之前的前置文章的可以先看零基础知识讲解。Episode 1Nim基础https://blog.csdn.net/2401_84512298/article/details/141559570?spm1001.2014.3001.5502Episode 2SG定理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 2004EA 和 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 值长什么样子再说。这里建议读者自己写一下程序找找规律#includebits/stdc.h#pragmaGCCoptimize(O3,unroll-loops)#pragmaGCCtarget(avx2,bmi,bmi2,lzcnt,popcnt)usingnamespacestd;#definelllonglong#defineendl\nll sg[205];boolhave[1005];intmain(){ios::sync_with_stdio(0);cin.tie(0);sg[0]0;cout0:sg[0]endl;for(inti1;i200;i){memset(have,0,sizeof(have));for(intj1;ji;j)if(__gcd(j,i)1)have[sg[i-j]]1;for(intj0;j1000;j)if(!have[j]){sg[i]j;break;}couti:sg[i]endl;}return0;}然后我们的输出长这样冒号左边为石子数右边为所对应的 SG 函数值读者此时发现我的天哪为什么石子个数是偶数蓝色的都是0 00然后那些质数橙红色感觉就像是编号一样一个一个往上加1 11不是质数只是加上之后才是从1 11开始加比较好看它刚好顶替了2 22的位置2 22虽然是质数但也是偶数所以变成0 00了更惊喜的是主播并不知道为什么。剩下的规律实在有点难所以主播偷偷去看了一下题解然后发现居然就是它的最小质因子的 SG 值。比如25 2525就取5 55的数值3 3377 7777就取7 77的值4 44。那就很简单了直接筛选一下质数然后把 SG 值全算出来就好了。代码#includebits/stdc.h#pragmaGCCoptimize(O3,unroll-loops)#pragmaGCCtarget(avx2,bmi,bmi2,lzcnt,popcnt)usingnamespacestd;#definelllonglong#defineendl\nintt,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;id1;for(intj2*2;j10000000;j2)np[j]1,fac[j]min(fac[j],2);for(inti3;i10000000;i){if(!np[i]){sg[i]id;for(intji*2;j10000000;ji)np[j]1,fac[j]min(fac[j],i);}}for(inti3;i10000000;i2)if(np[i])sg[i]sg[fac[i]];cint;while(t--){cinn;intsum0;for(inti1;in;i){cina[i];sum^sg[a[i]];}if(sum0)coutBob\n;elsecoutAlice\n;}return0;}习题https://www.hackerrank.com/contests/5-days-of-game-theory/challenges/a-chessboard-game/problem英文题解在评论区提供的 USACO Guide 的讲解当中如果各位想要我写这道题的题解就发评论里尽量更新。