五、求组合数
核心模板
根据下面公式来预处理出等式右边的组合数的值，那么等式左边就可以用等式右边已经算过的值来进行计算（有点像dp）。
//c[a][b]表示从a个苹果中选b个的方案数 for(int i=0;i<N;i++){ for(int j=0;j<=i;j++){ if(!j) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } }
如下
首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
typedef long long LL; //快速幂模版 int qmi(int a,int k,int p){ LL res=1%p; while(k){ if(k&1) res=res*a%p; k>>=1; a=(LL)a*a%p; } return res; } //预处理阶乘的余数和阶乘逆元的余数 fact[0]=infact[0]=1; for(int i=1;i<N;i++){ fact[i]=(LL)fact[i-1]*i%mod; infact[i]=(LL)infact[i-1]*qmi(i,mod - 2,mod)%mod; }
题目一
题目链接：885. 求组合数 I
5.1题目描述
5.2思路分析
利用模板1求解即可。
5.3代码实现
#include <iostream> using namespace std; const int N=2010,mod=1e9+7; int c[N][N]; int n; //求组合数 void solve(){ for(int i=0;i<N;i++){ for(int j=0;j<=i;j++){ if(!j) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } } } int main(){ cin>>n; solve(); while(n--){ int a,b; cin>>a>>b; cout<<c[a][b]<<endl; } return 0; }
题目二
题目链接：
886. 求组合数 II
5.4题目描述
5.5思路分析
利用模板2求解即可。
下图作者如图，侵删。
5.6代码实现
#include <iostream> using namespace std; typedef long long LL; const int N=100010,mod=1e9+7; int fact[N],infact[N]; //fact[i]存储i!%mod的值；infact[i]存储i!的逆元%mod的值 int n; //快速幂模板 int qmi(int a,int k,int p){ LL res=1%p; while(k){ if(k&1) res=res*a%p; k>>=1; a=(LL)a*a%p; } return res; } int main(){ cin>>n; fact[0]=infact[0]=1; //0!%mod和其逆元%mod的值为1 //预处理出fact[]和infact[] for(int i=1;i<N;i++){ fact[i]=(LL)fact[i-1]*i%mod; //求每个阶乘%mod的结果 infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod; //求每个阶乘的逆元%mod的结果 } while(n--){ int a,b; cin>>a>>b; cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl; //按照组合数公式进行计算 } return 0; }
六、博弈论
NIM游戏
给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。
定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0
题目一
题目链接： 891. Nim游戏
6.1题目描述
给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤105,1≤每堆石子数≤109
输入样例：
2 2 3
输出样例：
Yes
6.2思路分析
计算所有数的异或值，如果值不为0，则先手必胜，否则先手必败。
6.3代码实现
#include <iostream> using namespace std; int n; int main(){ cin>>n; int res=0; while(n--){ int x; cin>>x; res^=x; //计算所有数的异或值 } if(res) cout<<"Yes"<<endl; //如果值不为0，则先手必胜 else cout<<"No"<<endl; //否则，先手必败 return 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)。
有向图游戏的和
设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。
题目二
题目链接：893. 集合-Nim游戏
6.4题目描述
给定 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
6.5思路分析
详见代码注释。
6.6代码实现
#include <iostream> #include <cstring> #include <unordered_set> using namespace std; const int N=110,M=10010; int k,n; //k为可以取石子的方案数（即一次取多少个） int s[N],f[M]; //f[]存储每堆石子的sg值 //求石子数量为x的这一堆石子的sg值 int sg(int x){ if(f[x]!=-1) return f[x]; //如果该值已经被算过则直接返回 unordered_set<int> S; //存放x各个后继结点的sg值 //遍历k种取法 for(int i=0;i<k;i++){ int sum=s[i]; //sum为本次取法取多少个石子 if(x>=sum) S.insert(sg(x-sum)); //如果可以取，则将取后的后继结点的sg值加入S } for(int i=0;;i++){ //对S求mex，求出不在集合中的最小自然数 if(!S.count(i)) return f[x]=i; } } int main(){ cin>>k; for(int i=0;i<k;i++) cin>>s[i]; cin>>n; int ans=0; memset(f,-1,sizeof f); for(int i=0;i<n;i++){ int x; cin>>x; ans^=sg(x); //n堆石子的sg的值异或起来不为0，则先手必胜 } if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
七、约数个数和约数之和
下图作者如图，侵删。
int范围内的数最多约数个数约为1600个
核心模板
如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1) 约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
题目链接：
870. 约数个数
7.1题目描述
7.2思路分析
将每个数质因数分解，利用unordered_map进行存储所有pi及其指数，即每分解一个数，将分解后对应的pi的指数加上分解质因数的次数。
7.3代码实现
#include <iostream> #include <unordered_map> using namespace std; typedef long long LL; const int mod=1e9+7; int n; int main(){ cin>>n; unordered_map<int,int> hash; //存储每个pi和其指数 while(n--){ int a; cin>>a; for(int i=2;i<=a/i;i++){ //注意循环从2~a/i while(a%i==0){ hash[i]++; //i的指数++ a/=i; } } if(a>1) hash[a]++; //注意if位置 } LL ans=1; for(auto i:hash) ans=ans*(i.second+1)%mod; cout<<ans; return 0; }
