4.9 容斥原理
4.9.1 890. 能被整除的数
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。
输入格式
第一行包含整数 n 和 m。
第二行包含 m 个质数。
输出格式
输出一个整数，表示满足条件的整数的个数。
数据范围
1≤m≤16,
1≤n,pi≤109
输入样例：
10 2
2 3
输出样例：
7
#include<bits/stdc++.h> using namespace std; const int N=20; typedef long long LL; int n,m; int p[N]; int main() { cin>>n>>m; for(int i=0;i<m;i++) cin>>p[i]; int res=0; for(int i=1;i<1<<m;i++) { int t=1,cnt=0; for(int j=0;j<m;j++) { if(i>>j&1) { cnt++; if((LL)t*p[j]>n) { t=-1; break; } t*=p[j]; } } if(t!=-1) { if(cnt%2) res+=n/t; else res-=n/t; } } cout<<res<<endl; return 0; }
4.10博弈论
NIM游戏 —— 模板题 AcWing 891. Nim游戏
给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。
定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0
公平组合游戏ICG
若一个游戏满足：
由两名玩家交替行动；
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。
有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。
Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, 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)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。
有向图游戏的和 —— 模板题 AcWing 893. 集合-Nim游戏
设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。
4.10.1 891. Nim游戏
给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例：
2
2 3
输出样例：
Yes
#include<bits/stdc++.h> using namespace std; int main() { int n; int res=0; cin>>n; while(n--) { int x; cin>>x; res^=x; } if(res) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
4.10.2 892. 台阶-Nim游戏
现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤105,
1≤ai≤109
输入样例：
3
2 1 3
输出样例：
Yes
#include<bits/stdc++.h> using namespace std; int main() { int n; int res=0; cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; if(i%2) res^=x; } if(res) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
4.10.3 893. 集合-Nim游戏
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 k，表示数字集合 S 中数字的个数。
第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例：
2
2 5
3
2 4 7
输出样例：
Yes
#include<bits/stdc++.h> using namespace std; const int N=110,M=10010; int n,m; int s[N],f[M]; int sg(int x) { if(f[x]!=-1) return f[x]; set<int> S; for(int i=0;i<m;i++) { int sum=s[i]; if(x>=sum) S.insert(sg(x-sum)); } for(int i=0;;i++) if(!S.count(i)) return f[x]=i; } int main() { cin>>m; for(int i=0;i<m;i++) cin>>s[i]; fill(f,f+M,-1); cin>>n; int res=0; for(int i=0;i<n;i++) { int x; cin>>x; res^=sg(x); } if(res) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
4.10.4 894. 拆分-Nim游戏
给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n,ai≤100
输入样例：
2
2 3
输出样例：
Yes
#include<bits/stdc++.h> using namespace std; const int N=110; int f[N]; int sg(int x) { if(f[x]!=-1) return f[x]; set<int> S; for(int i=0;i<x;i++) for(int j=0;j<=i;j++) S.insert(sg(i)^sg(j)); for(int i=0;;i++) if(!S.count(i)) return f[x]=i; } int main() { int n; cin>>n; fill(f,f+N,-1); int res=0; for(int i=0;i<n;i++) { int x; cin>>x; res^=sg(x); } if(res) puts("Yes"); else puts("No"); return 0; }
