数论

1、判断质数

从定义出发，判断质数时间复杂度是O(n) , 注意<2的数不是质数也不是合数;

优化

我们发现一个x可以分解成2个数的乘积，一个小于等于
sprt(x) , 另一个大于等于sqrt(x);

所以可以只枚举较小的，时间复杂度O(sqrt(x));

细节：循环范围有3种写法
(1) i <= sqrt(n) (2) i * i <= n (3) i <= n / i;

这里建议第3种，第一种sqrt函数太慢，第二种i*i容易爆int

https://www.acwing.com/activity/content/code/content/9374395/

2、分解质因数

从小到大遍历每个数，if(x % i == 0) ， 就计算一下应该是
i ^ ? , 也就是while(n%i == 0) n /= i , s++; , 然后输出
i , s ，他表示n里有s个i

为什么确定i一定是质数 ， 因为枚举到i时，x里一定
不包括2~i - 1的质因子，因为x是i的倍数，所以也一定不包含2~i - 1的质因子，所以i一定是质数

时间复杂度O(n);

然后由于n里只有一个大于sqrt(n)的质因子，所以可以直接
枚举到sqrt(n) , 最后如果有剩下的数就直接输出

时间复杂度是O(sqrt(n));

https://www.acwing.com/activity/content/code/content/9377881/

3、筛质数

把所有的数存起来
2 3 4 5 6 7 8 9 10 11 12

2的倍数有4、6、8、10、12，把他们删掉(因为有因数2)
3的倍数有6、9、12，把他们删掉(因为他们有因数3)

这就是朴素筛法

时间复杂度：n / 2 + n / 3 + … + n / n;
= n * ( 1 / 2 + 1 / 3 + .. + 1 / n);
大约等于O( n log n )

埃氏筛法

我们可以只用质数来筛，因为一个数n一定至少包含一个质数因子

证明：我们把n除了1和n的一个因数记为d

如果d是质数，那我们已经找到了
如果d是合数，那对他分解质因数就可以出现质数

时间复杂度约等于O(n) ， 实际复杂度O(n log log n);

欧拉筛

我们发现在埃氏筛中15会被3筛1遍，会被5筛1遍 ， 我们的欧拉筛就是要保证每个数只被最小质因子筛一遍

关键的一行是if ( i % primej == 0 ) break，因为此时
i*pj的质因数分解里一定包含pj , 如果与后面的数相乘一定可以换成pj * 比i大的数 ， 所以(p[j+1]就不是最小质因子);

正确性

if ( i % pj == 0 )
pj一定是i的最小质因子，pj一定是pji的最小质因子
if ( i % pj != 0 )
pj一定小于i的所有质因子，pj一定是pji的最小质因子

为什么保证每个数都会被筛

对于合数x，假设pj是x的最小质因子，当i枚举到x / pj时，
就会筛掉x

https://www.acwing.com/activity/content/code/content/9380216/

对于上面的模板，还有一个问题就是为什么不用判断
j <= cnt;

因为如果i时合数就会在i % pj == 0时break ， 如果i是质数
那么p里面是包含i的，所以在i % i时会break;

4、约数

判断约数

使用与判断质数一样的方法即可，并且由于约数也是成对出现的所以可以只枚举到sqrt(n)
(一个约数是i，那他对应的约数就是n / i)

细节是如果i == n / i就不能把另一对数n / i放进来，因为这个数是一个平方数，比如36如果不加上面的判断，他的因数里就有2个6

时间复杂度O(sqrt(n))

https://www.acwing.com/activity/content/code/content/9381489/

约数个数

首先对n分解质因数
n = p1^a1 * p2^a2 * … * pk^ak;

那么他的每个约数d = p1^x1 * p2^x2 * … * pk^xk;
(分解质因数是为了表示最简形式 ， 保证满足上面式子)

x1的范围是0 <= x1 <= ai;

根据乘法原理因数个数就等于
(a1 + 1) * (a2 + 1) * … * (ak + 1);

https://www.acwing.com/activity/content/code/content/9385229/

约数之和

公式
(p1^0+p1^1+…+p1^a1) * … * (pk^0+pk^1+…+pk^ak);

我们把这个公式展开就是() + () + … + ()的形式

每个()的内容都可以看作从每个不同的()中各抽一项，就是
p1^x1 * p2^x2 * … * pk^xk;

正好满足约数的条件

上面的公式的求法
t = p*t + 1;

解释：一开始
t = 1
t * p + 1 = p + 1(加1是递推式中的+1)
(t * p + 1) * p = ( p + 1 ) * p = p^2 + p + 1;(同上)

https://www.acwing.com/activity/content/code/content/9385446/

5、最大公因数

基本性质：d|a , d|b , d|ax + by

a mod b = a - floor(a / b) * b = a - c * b;

核心：证明gcd(a , b) = (b , a mod b);
也就是gcd(a , b) = gcd(b , a - c * b);

对于左边的任意一个公约数d，也就是d|a , d|b

即证明d | a - c * b;

根据上面的基本性质可知d|a - c*b;

对于右边的一个公约数d，就是d|b , d|a - c*b;

即证明d | a;

d|a - c * b = d|a - c * b + c * b = d|a;

https://www.acwing.com/activity/content/code/content/9385714/

6、欧拉函数

φ(n)表示求1-n中与n互质的数(欧拉函数)

其实φ()是积性函数，就是φ(nm) = φ(n) * φ(m);
很好理解

对n分解质因数
n = p1^a1 * … * pk^ak;

φ(n) = φ(p1^a1) * … * φ(pk^ak);

其中与pk^ak不互质的有
pk , 2pk , … , pk^(ak-1) * pk;
共有pk^(ak - 1)项

也可以写成pk^ak / pk , 因为每pk个数中就有一个pk的倍数

所以φ(pk^ak) = pk^ak - pk^(ak - 1) = pk^ak *(1 - 1/pk);

把最后一个式子展开pk^ak - pk^ak/pk ， 等价于原式;

因此

φ(n) = φ(p1^a1) * … * φ(pk^ak);
=(p1^a1 - p1^(a1-1) ) * … * (pk^ak - pk^(ak-1));
=p1^a1(1- 1/p1) * … * pk^ak(1 - 1/pk);
=p1^a1…pk^ak * (1 - 1/p1) * … * (1-1/pk);
=n(1-1/p1)* … * (1- 1/pk);

公式:n*(1- 1/p1) * … * (1 - 1/pk);

但是这个式子有小数，所以还得化简

原答案：ans * (1 - 1/i)
= ans * (1 - 1/i) * i / i;
= ans * (i - 1) / i;

代码
https://www.acwing.com/activity/content/code/content/9395539/

7、筛法求欧拉函数

先写一个线性筛，分为3种情况讨论

1、质数
明显phi[i] = i - 1 , 因为i和自己不互质

2、i % pj == 0
设pj是m的最小质因子，m通过pj * i筛掉

phi[m] = m * ( 1 - 1/p1 ) * … * ( 1 - 1/pk );
= pj * i * ( 1 - 1/p1 ) * … * ( 1 - 1/pk );
=pj * phi[i];

3、 i % pj != 0;
因为pj是质数，i % pj != 0 表示i不是pj的倍数合数，那么
i和pj互质 ， 我们就可以利用欧拉函数是积性函数解题

phi[m] = phi[i*pj] = phi[i] * phi[pj] = phi[i] * ( pj - 1 );

代码
https://www.acwing.com/activity/content/code/content/9409772/

8、欧拉定理

如果a与n互质，则：a^phi(n) = 1 ( mod n )

假设1-n中所有与n互质的数是a1…aphi(n)

这里的每一个aa1 … aaphi(n)都与n互质

并且这里的数两两不同，可以用反证法

a * ai = a * aj
a * ( ai - aj ) = 0( mod n );
a^-1 * a * ( ai - aj ) = 0 * a^-1(mod n )
(ai - aj) = 0(mod n)
ai = aj,所以矛盾了

这里的集合在mod n意义下是相等的，因为2个集合的数mod n后都与n互质，而与n互质的数只有那phi(n)个，而我们2个集合都有phi(n)项，所以2个集合相等

也就是a^phi(n) * (a1…aphi(n)) 同余于 a1 … aphi(n)
而 (a1…aphi(n))和a1 … aphi(n）, 根据推出的结论可以消掉

也就是说a^phi(n) = 1(mod n);

9、费马小定理
当p是质数时，a^( p - 1 ) = 1(mod p)
就是欧拉定理，因为当p是质数是phi[p] = p - 1;

10、快速幂

快速求解a^b mod p , 1 <= a , b , p <= 1e9;

预处理a^2^0 , a^2^1 … a^2^log b这几个数

将a^b用这些数组合出来 ，即a^b = a^2^x1…a^2^xt;
= a^2^(x1 + … + xt) ， 即二进制表示

为什么b可以用a^2^0 , a^2^1 … a^2^log b这几个数表示

因为二进制可以表示所有数 ， 且一个数x在二进制下最多
表示成2^log(x)

k = ( 1001 )2 = 2 ^ 0 + 2 ^ 3;

时间复杂度就是O( log k )

处理这log k个数的方法

a^2^0就是a，已经给过了
a^2^1 = ( a^2^0 )^2;
…
a^2^t = ( a^2^(t-1) )^2;
也就是前一个数的平方

例子：4^5 mod 10;

4^2^0 = 4(mod 10);
4^2^1 = 6(mod 10)
4^2^2 = 6(mod 10);

5 = (101)2;

4^5 = 4^(101)2 = 4^(2^0 + 2^2) = 4^2^0 * 4^2^2
= 4 * 6 = 4(mod 10)

代码
https://www.acwing.com/activity/content/code/content/9413864/

11、逆元
(假定p是质数)

a / b % p = a * c % p , 我们就说c是b的mod p的乘法逆元

通俗的语言就是对于a ,b找出一个c，使得a / b == a * c
(mod p) , 这个c就是b在mod p下的逆元

根据之前的费马小定理可知b^(p - 1) = 1(mod p)

a / b % p = a / b * b^(p - 1) % p = a * b^(p - 2) % p;

判断无解

如果b不是p的倍数那么他们就互质，而如果b % p == 0
那么b * 任意数 = 0(mod p) , 不满足b^(p - 1) = 1(mod p)

12、逆元(p不是质数)

逆元的另一种表示形式：b * b^-1 = 1(mod p)

证明
将等式2边同时成b

a = a * b * c(mod p);
1 = b * c(mod p)
b * c = 1(mod p)

满足c这个条件的就是b的逆元，证毕

而b * c = 1(mod p)
等价于bx + py = 1;

(y一般为负数)

而求解出的x就是逆元，这个式子可以用下面说的exgcd求，
不过需要保证gcd(b ,p ) == 1 . 即b和p互质

因为exgcd解决的式子时ax + by = gcd(a , b)

https://www.acwing.com/activity/content/code/content/9414125/

13、裴蜀定理

任意正整数a，b , 对任意整数x，y , gcd(a , b)|ax + by
并且一定存在一组x，y，舍得ax + by = gcd(a , b)

对于第一点：因为a是gcd的倍数，b是gcd的倍数，所以他们的和是gcd的倍数

第二点就是exgcd算法实现

14、扩展欧几里得

求解ax + by = gcd(a , b)中，x和y的一组解

首先考虑边界b = 0 , 也就是ax + 0y = gcd(a , b) , 此时的
gcd等于a，所以x = 1 , y = 0是一组解

然后递归的时候把x，y要交换就是->exgcd(b , a%b , y , x)

接下来要求by + (a mod b)x = gcd;
而a%b等价与a - floor(a / b) * b

也就是上面式子等于by + (a - floor(a/b) * b)x = gcd;

然后分析a和b的系数
= ax + b(y - floor(a / b) * x )

就是把y更新为y - floor(a / b) * x即可

求通解

现在已经求出x,y使得ax + by = c;
通解：a(x - b/d) + b(y - a/d);

因为展开后是ax - ab/d + by - ba/d最终的值还是ax+by

https://www.acwing.com/activity/content/code/content/9414958/(ax - by也在这里)

exgcd的应用 -> 线性同余方程

求出x，使得a * x = b(mod m)

等价变形

ax = m*y + b;
ax - my = b;
y = -y;
ax + my = b;

ax+my = b就是exgcd解决的问题

有解的情况是gcd( a , m )|b , 因为a是最大公约数的倍数，m是最大公约数的倍数，所以他们拼在一起也是最大公约数的倍数;

我们exgcd返回的值是gcd , 我们只需要把系数扩大若干倍，就可以让gcd变成b，很明显是b / gcd倍

另外如果要保证答案在int范围内，我们%m即可

证明：

ax + my = b;
a(km + r) + my = b;
ar + m( y + ak ) = b;

所以x = x % m , y = y + ak等式结果不变

https://www.acwing.com/activity/content/code/content/9417096/

15、中国剩余定理(CRT)

m1,m2,…,mn两两互质 ， 要求
x = a1(mod m1) , … , x = ak(mod mk)的值

首先令M = m1……mk;
Mi = M / mi , Mi^-1表示Mi的逆

答案其实是x = a1M1M1^-1 + … akMkMk^-1;

因为当模数为m1时，除了第一个式子外所有的式子的值都为0 ， 第一个式子M1*M1^-1 = 1 , 也就是第一个式子
就等于a1 , 后面每一项都可以这样考虑

求逆：(ax = 1(mod p) , 那么x就是a在mod p情况下的逆)

可以转化成ax + py = 1,这里的条件就是a和p必须互质

也就是要求Mi和模数两两互质

由于Mi表示不带当前模数的所有模数的乘积，且他们两两互质，所以Mi与模数互质

最小整数解

看一个例子x = 2(mod 3) , x = 3(mod 4) , x的最小整数解为11，后面的每个解都依次加12

这个12其实是3,4的最小公倍数，因为12同时是3,4的倍数，
所以加12，在取模的意义下是为0的

所以如果求出的解不是最小整数解，那么就mod M
(因为模数两两互质，最小公倍数就是他们的乘积)

16、扩展中国剩余定理(EXCRT)

当m不满足两两互质时，就要用到EXCRT

先考虑2个方程

x mod a1 = m1 , x mod a2 = m2;

变形：x = k1 * a1 + m1 , x = k2 * a2 + m2;

可知k1 * a1 + m1 = k2 * a2 + m2;

移项：k1a1 - k2a2 = m2 - m1;

由于只有k1,k2不已知，所以可以用exgcd求解

有解等价于gcd(a1 , a2) | m2 - m1;

如果求出了k1 , 那么x = k1*a1 + m1;

然后求通解，通解可以参考exgcd里加法的通解
(d = 最大公约数)

k1 + k * a2/d
k2 + k * a1/d;

然后再把k1的通解带入原方程

x = k1 * a1 + m1 = (k1 + k * a2/d) * a1 + m1;

整理
x = a1k1 + m1 + k * a1a2/d;
x = a1k1 + m1 + k * lcm(a1 , a2 );
把a1k1 + m1记为x0 并且 lcm(a1 , a2)记为a;

x = x0 + ka ,我们发现他和x = k1 * a1 + m1结构一样，可以进行合并，最后的式子是x = ka + x0;

这个方程的最小值为x0 mod a;

https://www.acwing.com/activity/content/code/content/9421901/

17、高斯消元

题目：https://www.acwing.com/problem/content/885/

解有3种情况(1)无解 (2)无数多组解 (3)唯一解

把系数抽出来变成正方形(不算b1)

初等行列变换(等价变换)
(1）把某一行乘上k(k不等于0)
(2) 交换2行
(3) 把某一行乘上k,加到另一行

最后要把矩阵变成上三角形式

a1x1 + … + amxn = b1;
a2x2 + … + amxn = b2;
…
xn = bn;

这样倒推就能求出每个x；

(1)完美阶梯型：唯一解
(2)0 = 非0：无解
(3)0 = 0：无穷多组解

模拟样例
1 2 -1 -6
2 1 -3 -9
-1 -1 2 7

高斯消元算法步骤
枚举每一列c
(1)找到当前这列绝对值最大的一行(保证精度)
(并且不找已经固定的行)
(2)将该行移到最上面
(3)将该行第一个数变成1
(4)将下面所有行的当前列消成0;

上面对应的每一步：

2 1 -3 -9
1 2 -1 -6
-1 -1 2 7

1 0.5 -1.5 -4.5
1 2 -1 -6
-1 -1 2 7

1 0.5 -1.5 -4.5
0 1.5 0.5 -1.5
0 -0.5 0.5 2.5

思路并不难，难点在代码实现上

https://www.acwing.com/activity/content/code/content/9330855/(详细注释)

异或线性方程组

题目：https://www.acwing.com/problem/content/886/

由于异或相当于只有0和1不进位的加法
(1^1 = 0 , 1 + 1 = 2)
或者是mod 2加法
(1 + 1 = 2 , 1 + 1 mod 2 = 0 );

所以可以用类似高斯消元的方法做

(1)消成上三角矩阵
(a)枚举列
(b)找到非0行
(c)交换
(d)消成0
(2)判断
(a)完美：唯一解
(b)有矛盾：无解
(c)无矛盾：无穷解

有很多证明在代码里

https://www.acwing.com/activity/content/code/content/9431117/

19、求组合数

求组合数I

https://www.acwing.com/problem/content/887/

数据范围：10w组 1 <= m <= n <= 2000 递推 n^2

直接的组合数公式C(n,m) = n! / n!(n - m)!;

如果直接套公式时间复杂度：10000020000 = 210^8

有点太慢了，但是我们可以预处理所有a,b的情况
一共有2000^2 = 4 * 10^6种;

预处理方法(递推)

递推式：C(n ,m) = C(n - 1 , m) + C(n - 1 , m - 1);

有一堆apple , 其中有一个apple: p; , 包含p的情况是C(n-1,m-1) , 不包含p的情况是C(n - 1 , m);

时间复杂度是O(N ^ 2) ，注意不是n，而是a、b的最大值;

https://www.acwing.com/activity/content/code/content/9431467/

求组合数||

https://www.acwing.com/problem/content/888/

数据范围:1w组,1 <= b <= a <= 10^5 预处理 N log mod
(数据个数可以到十万，这里为了照顾Java同学)

我们发现可以预处理阶乘，但是有些情况下
(a % p) / (b % p) % p != a / b % p;

我们就可以用逆元的知识把除法变成乘法

所以我们可以预处理阶乘数组fact , 逆元数组inv;

最后C(a ,b) = fact(a) * inv(a - b) * inv(b);

https://www.acwing.com/activity/content/code/content/9433642/

求组合数|||

https://www.acwing.com/problem/content/889/

20组 1 <= b <= a <= 10^18 , 1 <= p <= 1e5 , Lucas
logp N * p * log p;

Lucas定理(组合数取模问题)：
C(a , b) = C(a mod p , b mod p ) * C(a / p , b/p)(mod p)

Lucas定理不需要掌握证明

代码实现：我们发现p很小，所以小于p的数，用定义做，然后C(a / p , b / p)递归去算就行

https://www.acwing.com/activity/content/code/content/9434376/

求组合数IV

https://www.acwing.com/problem/content/890/

1 <= b <= a <= 5000 , 且没有模数，高精度

公式：C(a , b) = a! / b!(a - b)!

当然不能直接高精度因为高精除以高精太麻烦了，并且运行速度太低

我们可以先对C(a ,b)分解质因数
=p1^a1 * p2^a2 * … * pk^ak;

这样就可以只写一个mul函数、效率高、好写

我们可以先把数据范围内的质数晒一下(<= 5000的质数)
筛出的质数命名为p数组

计算项数数组(a1…ak)的时候
用在a!中p出现的个数 - b!(a - b)!中p出现的个数

就是p出现的次数

最后一个问题就是求n!中包含多少个因子p

a!包含p的个数 = floor(a /p) + floor(a / p^2) + …
(直到p^x大于a)；

由于p是质数，只有他是p的倍数才能有因子p

就比如说p^k , 他再算p的时候加1次，算p^2的时候加一次… , 一定加了k次，这是正确的

https://www.acwing.com/activity/content/code/content/9434799/

20、卡特兰数

https://www.acwing.com/problem/content/891/

咱们可以把这些把这个位置是1还是0对应到矩阵上，图

https://cdn.luogu.com.cn/upload/image_hosting/m08cou0u.png

我们发现如果想让走法满足条件，就是x >= y(因为x是0，y是1 ， 要求0的个数大于1的个数)

如果没有这个条件答案是C(12 , 6);

然后对于不合法的方案我们给他折叠一下

https://cdn.luogu.com.cn/upload/image_hosting/lp6wr58b.png

黄色是原不合法路径，绿色是弯折后的路径，我们发现，从0,0出发的不合法走法最终都能对应到5 , 7;

答案:C(12 , 6) - C(12 , 5);
替换成n：总能到(n-1,n+1),C(2n , n) - C(2n , n - 1);

https://www.acwing.com/activity/content/code/content/9435143/

21、容斥原理

https://cdn.luogu.com.cn/upload/image_hosting/n1hp9edo.png

求解这些圆的占地面积,相当于并集

最直观的思路

S1 + S2 + S3 - S1^S2 - S1^S3 - S2^S3;

但是我们观察7号部分被加了3次，被减了3次，所以还需要加上7号部分，即S1^S2^S3

答案就是
S1 + S2 + S3 - S1^S2 - S1^S3 - S2^S3 + S1^S2^S3;

2个圆
S1 + S2 - S1^S2;

4个圆
S1 + S2 + S3 + S4;
-S1^S2 - S1^S3 - S1^S4 - S2^S3 - S2^S4 - S3^S4;
+S1^S2^S3 + S1^S2^S4 + S1^S3^S4 + S2^S3^S4;
-S1^S2^S3^S4;

我们发现奇数个数的集合会被加上(S1^S2^S3)，偶数个数的集合会被减去(S1^S2)

奇加偶减，这就是容斥原理

计算一共有多少项
C(n,1) + C(n,2) + … + C(n , n);

但是这样不好算我们可以在前面填一个C(n , 0);
C(n , 0) + C(n,1) + C(n,2) + … + C(n , n);

这样就等于从集合里选任意个数的方案数，每个集合都有选和不选2种抉择，根据乘法原理有2^n个集合

但是C(n,0)是后加上的所以2^n - C(n ,0) = 2^n - 1;

证明奇加偶减是对的，即证明

|S1 U S2…Sn| = sum(i)|Si| - sum(i,j)|Si ^ Sj| + ....;

我们设x出现了k个集合中(1 <= k <= n)
哪x会被算

C(k,1) - C(k,2) + C(k,3) + … + (-1)^(k-1)C(k , k) = 1次

而上面式子的结果等于1，可以用二项式定理证明
(在组合数学笔记中记录过二项式定理)

(1-1)^k = sum(i = 0 , k) C(k,i) * （-1)^i;

即sum(i = 0 , k) C(k,i) * （-1)^i = 0;

把i=0的项分出来
C(k,0)(-1)^0 + sum(i = 1 , k) C(k,i) *(-1)^i = 0;

1 + sum(i = 1 , k) C(k,i) *(-1)^i = 0;

sum(i = 1 , k) C(k,i) *(-1)^i = -1;

将等式2边同时乘-1

sum(i = 1 , k) C(k,i) *(-1)^(i-1) = 1;

这就是原来的式子

例题
https://www.acwing.com/activity/content/code/content/9435537/

22、博弈论

概念

公平组合游戏ICG

1、2名玩家交替行动
2、在游戏任意时刻，可以执行的合法行动与轮到哪一名玩家无关
3、不能行动的玩家判负

Nim博弈就是公平组合游戏，而像围棋就不是公平组合游戏，因为一方只能动白子，另一方只能动黑子，不满足2

有向图游戏

给定一个DAG , 图中有一个唯一的起点，在起点上放有一枚棋子，2名玩家沿有向边移动

每次可以移动一次，无法移动的判负

任何一个ICG都可以转化成有向图游戏：把一个局面看做图中的一个节点，每个节点像合法的下个局面连有向边

Nim游戏

https://www.acwing.com/problem/content/893/

模拟样例

先手先在有3堆石子那堆拿一个，后面后手怎么做我就怎么做
(后手拿1，我拿一个，后手拿2，我拿2个)

概念

先手必胜状态：拿走一些石子后可以使xor值变成0
先手必败状态：随便拿走一些石子后会使xor值变成非0
(再下面描述中去掉了先手这2个字，xor值见下文)

结论(a是石子个数)

a1 xor a2 xor … xor an = 0(先手必败，否则必胜)

(1) 0 xor 0 xor … xor 0 = 0;
(2) a1 xor a2 xor … xor an = x (x不等于0)
(3) a1 xor a2 xor … xor an = 0

第二种情况就是证明可以从一堆石子，拿走一些石子，可以使异或值变成0，即后手一定是必败状态

假设x二进制表示中的最高一位在第k位，那么a1-an中必有一个ai,第k位是1 ， 并且ai xor x < ai;

此时可以拿走ai - (ai xor x)个石子，还剩ai - (ai - (ai xor x) )个石子 ， 开括号也就是ai xor x个石子

然后把ai更新一下，变成ai ^ x , 然后因为异或满足交换律，所以可以把x放到最后，前面仍然是一堆ai

这样前面一堆ai是x，后面还有一个x，x xor x = 0
就把异或值变成了0

第三种情况就是证明从一堆石子里拿走若干个，异或值不是0;
即留给后手是必胜状态

用反证法

假设玩家从第i堆石子拿走若干个结果仍然为0 ， 不妨设还剩下
a’个石子，因为不能不拿所以0 <= a’ < a;

(a1 xor a2 xor … xor ai xor … xor an) xor
(a1 xor a2 xor … xor a’ xor… xor an)

= ai xor a’ = 0 xor 0 = 0;

我们推出ai == a’所以矛盾

基于上面的证明我们得出如下结论：

如果最开始异或值是0，那么先手的异或值永远是0，后手永远不是0

如果最开始异或值不是0，那么先手的异或值永远不是0，后手永远是0

如果先手的异或值不为0，那么后手的异或值为0，如果先手的异或值为0，那么后手的异或值不为0

而最终的失败状态是(1) , 所以如果一个人在拿石子时异或值永远不为0，就一定不会是失败者

所以可以求出一开始所有a的异或值，if(异或值)puts(“Yes”);
else puts(“No”);

https://www.acwing.com/activity/content/code/content/9436779/

SG函数

概念

Mex运算

设S为1个非负整数集合，定义mex(S)为求出不属于集合S的最小非负整数的运算，即

mex(S) = min{x},那么x是自然数，且不属于S

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，每条边分别到达y1,y2,…,yk

定义SG(x)为x的后继节点y1,y2,…,yk的SG值构成的集合再执行mex(S)的效果，即

SG(x) = mex({SG(y1) , SG(y2) , … , SG(yk)});

其中SG(终点)一定等于0;

SG定理
一个游戏的SG函数值等于各个子游戏的SG函数值的异或和

举例
https://cdn.luogu.com.cn/upload/image_hosting/6uhjbexn.png

对于一张图来讲，SG(x) = 0为必败态，否则是必胜态

证明：SG(x) = 0, 说明x所能转移的y都不存在SG(y) = 0 , 即不不能使对方处于必败态

SG(x)不等于0 ， 说明存在一个状态y，使得SG(y) = 0,即可以使对方处于必败态

但是一般的应用是在多个图上做操作

在多个图上做操作的结论是

SG(x1) xor SG(x2) xor … xor SG(xn) = 0(先手必败,反之必胜)

这个证明可以用类似Nim游戏的方法

(基本一样，所以这里的语言逻辑性不强，这里的所有语言都可以参照Nim游戏的证明)

(1)SG(xi) = 0 , xor = 0;
(2)xor != 0

那么一定能找到xi使得SG(xi) xor x < SG(xi)，我们知道
SG(x) = k , 那么他可以遍历到0 - (k - 1)任意一个数

所以SG(xi)这个局面，一定可以走到SG(xi) xor x这个局面
那把SG(xi)变成SG(xi) xor x后，那么就可以把xor变成1

(3)xor = 0;

用之前的反证法，会得出SG(xi) = k可以走到k这个局面;
出现了矛盾，所以下一轮xor = 非0

https://www.acwing.com/activity/content/code/content/9438493/

例题

Nim：https://www.acwing.com/activity/content/code/content/9441057/

SG:
https://www.acwing.com/activity/content/code/content/9441335/