第四章 数学知识
主要内容:数论,组合数学,高斯消元,简单博弈论
质数
试除法
试除到根号n。
模板:试除法判定质数
bool is_prime(int x){
if(x<2)return false;
for(int i=2;i<=x/i;i++){
if(x%i==0)return false;
}
return true;
}
分解质因数:也是试除法
模板:试除法分解质因数
void divide(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0){
int s=0;
while(x%i==0){
s++;
x/=i;
}
cout<<i<<' '<<s<<endl;
}
}
if(x>1)cout<<x<<' '<<1<<endl;
cout<<endl;
}
筛质数
埃式筛法:筛质数,删掉倍数。
从2-n的自然数,第一次删掉2的倍数,2、4、6……
然后是3的倍数……
时间复杂度计算:
$$
\text{第一次:}\frac{n}{2},\text{第二次:}\frac{n}{3},\cdots
$$
$$ \text{总:}S=\frac{n}{2}+\frac{n}{3}+\cdots =n\left( \frac{1}{2}+\frac{1}{3}+\cdots \frac{1}{n} \right) =n\left( \ln n+C \right) $$
模板:朴素筛法
int primes[N],cnt;
bool st[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(st[i])continue;
primes[cnt++]=i;
for(int j=i+i;j<=n;j+=i){
st[j]=true;
}
}
}
优化版就是只删质数的倍数
质数定理:1-n中只有 n/ logn个质数
还有一种,线性筛法:从小到大筛选质数,n只会被它的最小质因子筛掉
$$
p_j\times i
$$
证明:
- 从小到大筛选质数 $p_j$
- 如果 $p_j$ 整除 $i$ ,则 $p_j$ 一定是 $i$ 的最小质因子,则 $p_j$ 一定是 $p_j\times i$ 的最小质因子
- 如果 $p_j$ 不整除 $i$ ,则 $p_j$ 一定小于 $i$ 的所有质因子,则 $p_j$ 一定是 $p_j\times i$ 的最小质因子
模板
int primes[N],cnt;//primes[N]存储所有质数,cnt存储数量
bool st[N];//存储当前数是否被筛掉了,没筛为false,为质数
//得到1-n之间的所有质数
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i])primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0)break;
}
}
}
约数
试除法,枚举根号n次,利用约数是成对出现的特点
模板:
vector<int> get_divisors(int x){
vector<int> res;
for(int i=1;i<=x/i;i++){
if(x%i==0){
res.push_back(i);
if(i !=x/i)res/push_back(x/i);
}
}
sort(res.begin(),res.end());
return res;
}
算术基本定理
设一个自然数的质因数分解如下
$$
N=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}
$$
则此自然数的约数个数为:
$$
\left( \alpha _1+1 \right) \left( \alpha _2+1 \right) \cdots \left( \alpha _k+1 \right)
$$
约数之和为:
$$
\left( p_1^0+p_1^1+\cdots +p_1^{\alpha _1} \right) \left( p_2^0+p_2^1+\cdots +p_2^{\alpha _2} \right) \cdots \left( p_k^0+p_k^1+\cdots +p_k^{\alpha _k} \right)
$$
欧几里得算法:辗转相除法
时间复杂度:$O\left( \log N \right)$
根相减损术
模板: 求a和b的最大公约数
int gcd(int a,int b){
return b ? gcd(b,a%b) : a;
}
欧拉函数
$\varphi \left( N \right)$ :1~N中与N互质的数的个数
公式:
$$
N=p_1^{\alpha _1}p_2^{\alpha _2}\cdots p_k^{\alpha _k}
$$
$$ \varphi \left( N \right) =N\left( 1-\frac{1}{p_1} \right) \left( 1-\frac{1}{p_2} \right) \cdots \left( 1-\frac{1}{p_k} \right) $$
证明:
- 本质和筛质数很相似,将N质因数分解
- 对每个质因数 $p_i$ ,筛掉他的倍数。剩下的就是 $\varphi \left( N \right)$
- 公式通过容斥原理得出,即设 $P_i$ 为 $p_i$ 倍数的集合
$$ \begin{aligned} \varphi \left( N \right) &=N\left( 1-\bigcup_{i=1}^k{P_i} \right)\\ &=\left( 1-\sum_{j=1}^k{\left( -1 \right) ^{j-1}\prod_{1\le a_1<\cdots <a_j\le k}{\frac{1}{p_{a_1}p_{a_2}\cdots p_{a_j}}}} \right)\\ &=N\left( 1-\frac{1}{p_1} \right) \left( 1-\frac{1}{p_2} \right) \cdots \left( 1-\frac{1}{p_k} \right) \end{aligned} $$
欧拉定理
对任意两个正整数 $a$ , $n$ ,如果两者互质,那么 $a^{\varphi \left( n \right)}\equiv 1\left( \text{mod\ }n \right)$
朴素求法:直接分解质因数
int phi(int x){
int res=x;
for(int i=2;i<=x/i;i++){
if(x%i==0){
res = res/i*(i-1);//先除,后乘,防止溢出
while(x%i==0)x/=i;
}
}
if(x>1)res=res/x*(x-1);
return res;
}
线性筛法求1~n之间的欧拉函数
证明:
-
若i为质数,则
eular[i]=i-1
-
从小到大遍历 $p_j$ ,设 $p_j\times i=t$
-
若 $p_i$ 整除 $i$ ,则 $p_i$ 也为 $t$ 的最小质因子,由于 $\varphi \left( i \right) =i\left( 1-\frac{1}{p_j} \right) \left( 1-\frac{1}{p_{j+1}} \right) \cdots \left( 1-\frac{1}{p_k} \right)$ ,
则 $\varphi \left( t \right) =p_ji\left( 1-\frac{1}{p_j} \right) \left( 1-\frac{1}{p_{j+1}} \right) \cdots \left( 1-\frac{1}{p_k} \right) =p_j\varphi \left( t \right)$
-
若 $p_i$ 不整除 $i$ ,则 $p_i$ 也为 $t$ 的最小质因子,且小于 $i$ 的最小质因数,由于 $\varphi \left( i \right) =i\left( 1-\frac{1}{p_1} \right) \left( 1-\frac{1}{p_2} \right) \cdots \left( 1-\frac{1}{p_k} \right)$
则 $\varphi \left( t \right) =p_ji\left( 1-\frac{1}{p_j} \right) \left( 1-\frac{1}{p_1} \right) \left( 1-\frac{1}{p_2} \right) \cdots \left( 1-\frac{1}{p_k} \right) =p_ji\left( 1-\frac{1}{p_j} \right) \varphi \left( t \right) =\left( p_j-1 \right) \varphi _i$
模板:
int primes[N],eular[N],cnt;//primes[N]存储所有质数,eular[N]存储每个数的欧拉函数值
bool st[N];//st[N]存储x是否被筛掉
void get_eular(int n){
eular[1]=1;
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
eular[i]=i-1;//素数的欧拉函数为本身减一
}
for(int j=0;primes[j]<=n/i;j++){
int t =primes[j]*i;
st[t]=true;
if(i%primes[j]==0){
eular[t]=eular[i]*primes[j];
break;
}
else{
eular[t]=eular[i]*(primes[j]-1);
}
}
}
}
快速幂
目的:快速求出来a的k次方mod b的结果
在O(log k)复杂度内
主要利用二进制的优势,每次翻倍平方
例如求 $a^k\ \text{mod\ p}$ ,先求 $a^{2^0}\ \text{mod\ }p$ ,再求 $a^{2^1}\ \text{mod\ }p,a^{2^2}\ \text{mod\ }p…,a^{2^{\log _k}}\ \text{mod\ }p$
模板:
//求m^k mod p ,时间复杂度O(log k)
int qmi(int m,int k,int p){
int t=m,int res=1;
while(k){
if(k&1)res = res*t%p;
t = t*t%p;
k >>=1;
}
return res;
}
费马小定理
若存在整数 $a,p$ ,$a$ 为整数, $p$ 为质数,那么 $a^{p-1}\equiv 1\left( \text{mod\ }p \right)$
费马小定理是欧拉定理的一种特殊情况(当 $n$ 为质数时 $\varphi \left( n \right)$ 为$n-1$)
逆元定义
若整数 $b,m$ 互质,并且对于任意的整数 $a$ ,如果满足 $b|a$ ,则存在一个整数 $x$ ,使得 $\frac{a}{b}\equiv a\times x\left( \text{mod\ }m \right)$ ,则称 $x$ 为 $b$ 的模 $m$ 乘法逆元,记为 $b^{-1}\left( \text{mod\ }m \right)$
$b$ 存在乘法逆元的充要条件是 $b$ 与模数 $m$ 互质。当模数 $m$ 为质数时,$b^{m-2}$ 即为 $b$ 的乘法逆元
证明:
$$
\frac{a}{b}\equiv ab^{-1}\left( \text{mod\ }m \right) \rightarrow b\frac{a}{b}\equiv abb^{-1}\left( \text{mod\ }m \right) \rightarrow bb^{-1}\equiv 1\left( \text{mod\ }m \right)
$$
由费马小定理 $b^{m-1}\equiv 1\left( \text{mod\ }m \right)$ ,则 $b^{-1}=b^{m-2}$
扩展欧几里得算法
裴蜀定理
是一个关于最大公约数的定理
设 $a,b$ 是不全为零的整数,则存在整数 $x,y$ ,使得 $ax+by=\text{gcd}\left( \text{a,b} \right)$
变式:
设 $a,b$ 为两个互质数,即$(a,b)=1$ ,则存在整数 $x,y$ ,使得 $ax+by=1$
证明过程中就是利用了欧几里得算法辗转相除,同时存储 $x,y$ ,即变为扩展欧几里得算法
推导:
-
若 $b=0$ , $(a,0)=a$ , 即 $a\times x+0\times y=a$ , $x=1,y=0$
-
若 $b\ne 0$ , $(a,b)=d$ , 即 $b\times y+a\left( \text{mod\ }b \right) \times x=\text{gcd}\left( a,b \right)$
即 $by+\left( a-\lfloor \frac{a}{b} \rfloor b \right) x=d$ , 即 $ax+b\left( y-\lfloor \frac{a}{b} \rfloor x \right) =d$
得到:
$$
\left\{ \begin{array}{l}
x=x\\
y=y-\lfloor \frac{a}{b} \rfloor x\\
\end{array} \right.
$$
模板:扩展欧几里得
//求x,y,使得ax+by = gcd(a,b)
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
else{
int d = exgcd(b,a%b,y,x);
y -=a/b*x;
return d;
}
}
中国剩余定理
定理(CRT)
设正整数 $m_1,m_2,\cdots ,m_k$ 两两互素,则同余方程组:
$$
\left\{ \begin{array}{c}
x\equiv a_1\left( \text{mod\ }m_1 \right)\\
x\equiv a_2\left( \text{mod\ }m_2 \right)\\
\begin{array}{c}
x\equiv a_3\left( \text{mod\ }m_3 \right)\\
\vdots\\
x\equiv a_k\left( \text{mod\ }m_k \right)\\
\end{array}\\
\end{array} \right.
$$
有整数解。并且在 $\text{mod\ }M=m_1\times m_2\times \cdots \times m_k$ 下的解是唯一的。
解为 $x= a_1M_1M_{1}^{-1}+a_2M_2M_{2}^{-1}+\cdots +a_kM_kM_{k}^{-1} \left( \text{mod\ }M \right)$
其中 $M_i=\frac{M}{m_i},M_{i}^{-1}$ 为 $M_i\left( \text{mod\ }m_i \right)$ 的逆元
例题 表达整数的奇怪方式
链接:AcWing 204. 表达整数的奇怪方式 - AcWing
证明:
由于 $m_i<a_i$ ,方程等价于
$$
\left\{ \begin{array}{c}
x\ \text{mod\ }a_1=m_1\\
x\ \text{mod\ }a_2=m_2\\
\vdots\\
x\ \text{mod\ }a_n=m_n\\
\end{array} \right.
$$
对于其中任意两项,都可以合并成一个新的相似的表达式(下面会证明)。这里以前两项为例,即存在 $k1,k2$ ,使得
$$
\left\{ \begin{array}{c}
x=k_1a_1+m_1\\
x=k_2a_2+m_2\\
\end{array} \right.
$$
消去 $x$ ,$k_1a_1-k_2a_2=m_2-m_1$ 。记 $(a,b)=d$ ,若 $d\left| m_2-m_1 \right.$ ,则 $k_1,k_2$ 有解,通解为:
$$
\left\{ \begin{array}{c}
k_1=\hat{k}_1+k’\frac{a_2}{d}\\
k_2=\hat{k}_2+k’\frac{a_1}{d}\\
\end{array} \right.
$$
于是,
$$
x=\left( k_1+k’\frac{a_2}{d} \right) a_1+m_1
=k’\frac{a_1a_2}{d}+k_1a_1+m_1
$$
令 $a’=\frac{a_1a_2}{d}$ , $m’=k_1a_1+m_1$
于是前两式子合并为 $x=k’a’+m’$
代码:
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y){
if(!b){
x=1,y=0;
return a;
}
else{
LL d=exgcd(b,a%b,y,x);
y -=a/b*x;
return d;
}
}
int main()
{
int n;
scanf("%d", &n);
LL x=0,a1,m1;
cin>>a1>>m1;
n--;
bool flag=true;
while(n--){
LL a2,m2;
cin>>a2>>m2;
LL k1,k2;
LL d =exgcd(a1,a2,k1,k2);
if((m2-m1)%d){
flag=false;
break;
}
k1 *=(m2-m1)/d;
LL t = a2/d;
k1 = (k1%t+t)%t;//缩小k1
x=a1*k1+m1;
//更新m1,a1
m1 = a1*k1+m1;
a1 = abs(a1/d*a2);
}
if(flag){
x = (m1%a1+a1)%a1;
cout<<x<<endl;
}
else printf("-1\n");
return 0;
}
高斯消元
时间复杂度 $O(n^3)$
本质就是初等行列变换
算法流程:
- 枚举每一列 $c$
- 找到绝对值最大的一行
- 将该行换到最上面
- 将该行第一个数变成1
- 将下面所有行的第 $c$ 列消成0
- $r++$
- 若 $r<n$ ,则,查看是否有 $0=$ 非零的情况,有则为无解;无则为无穷解
- 最后,若 $r=n$ ,有唯一解,倒着推出答案
模板(浮点数版)
// a[N][N]是增广矩阵
int gauss()
{
int c, r;
for (c = 0, r = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ ) // 找到绝对值最大的行
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;//如果绝对值最大为0,则continue
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
if (r < n)
{
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps)
return 2; // 无解
return 1; // 有无穷多组解
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0; // 有唯一解
}
int t=gauss();
if(t==2)printf("No solution\n");
else if(t==1)printf("Infinite group solutions\n");
else{
for(int i=0;i<n;i++){
if(fabs(a[i][n])<eps)a[i][n]=0;//去除输出-0.00情况
printf("%.2lf\n",a[i][n]);
}
}
位运算版
int gauss(){
int r,c;
for(r=0,c=0;c<n;c++){
int t=r;
//找到一个非0即可
for(int i=r;i<n;i++){
if(a[i][c]){
t=i;
}
}
if(!a[t][c])continue;
for(int i=c;i<=n;i++)swap(a[r][i],a[t][i]);//交换
for(int i=r+1;i<n;i++){//无需变1,因为本来就是非0即1
if(a[i][c])
for(int j=n;j>=c;j--){
a[i][j] ^=a[r][j];
}
}
r++;
}
if(r<n){
for(int i=r;i<n;i++){
if(a[i][n])return 2;
}
return 1;
}
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
a[i][n]^=a[i][j]*a[j][n];
}
}
return 0;
}
int t=gauss();
if(t==2)printf("No solution\n");
else if(t==1)printf("Multiple sets of solutions\n");
else{
for(int i=0;i<n;i++){
printf("%d\n",a[i][n]);
}
}
求组合数
第一种:10万组询问,a和b的范围2000以内,利用递推式
$$ C_{a}^{b}=C_{a-1}^{b}+C_{a-1}^{b-1} $$
模板:递推法求组合数
//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;
}
}
第二种:1万组询问,a和b范围为10的五次方
回归定义,
$$
C_{a}^{b}=\frac{a!}{b!\left( a-b \right) !}
$$
通过预处理逆元的方式求组合数
//首先预处理出所有阶乘取模的余数fact[N],以及所有阶乘的取模的逆元infact[N]
//如果取模的数为质数,可以用费马小定理求逆元
int qmi(int m,int k,int q){
int res=1,t=m;
while(k){
if(k&1)res=(LL)res*t%q;
t = (LL)t*t%q;
k >>=1;
}
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;
}
第三种:20组,a和b范围 $10^{18}$ ,给定p,范围 $10^5$ ,利用卢卡斯定理
卢卡斯定理:
$$
C_{a}^{b}=C_{a\ \text{mod\ }p}^{b\ \text{mod\ }p}C_{a/p}^{b/p}\left( \text{mod\ }p \right)
$$
其中 $a=a_kp^k+a_{k-1}p^{k-1}+\cdots +a_0p^0$ ,$b=b_kp^k+b_{k-1}p^{k-1}+\cdots +b_0p^0$
即 $C_{a}^{b}=C_{a_k}^{b_k}C_{a_{k-1}}^{b_{k-1}}\cdots C_{a_0}^{b_0}$
时间复杂度: $\log _pN\times p\log p$
若p是质数,则对于任意整数 1 <= m <= n,有:
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int p;
int qmi(int m,int k){
int res=1;
while(k){
if(k&1)res=(LL)res*m%p;
m=(LL)m*m%p;
k >>=1;
}
return res;
}
int C(int a,int b){
int res=1;
for(int i=1,j=a;i<=b;i++,j--){
res =(LL)res*j%p;
res =(LL)res*qmi(i,p-2)%p;
}
return res;
}
int lucas(LL a,LL b){
if(a<p && b<p)return C(a,b);
else return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
高精度直接求组合数,ab范围5000
$a$ 阶乘中分解质因数 $p$ 的次数为:
$$
a!=p_{k}^{S_k}p_{k-1}^{S_{k-1}}\cdots p_{1}^{S_1}
$$
$$ S_k=\lfloor \frac{a}{p_{k}^{1}} \rfloor +\lfloor \frac{a}{p_{k}^{2}} \rfloor +\lfloor \frac{a}{p_{k}^{3}} \rfloor +\cdots $$
模板:
当我们需要求出组合数的真实值,而非对某个数的余数时,分解质因数的方式比较好用:
1. 筛法求出范围内的所有质数
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
3. 用高精度乘法将所有质因子相乘
int primes[N], cnt; // 存储所有质数
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否已被筛掉
void get_primes(int n) // 线性筛法求素数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p) // 求n!中的次数
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
vector<int> mul(vector<int> a, int b) // 高精度乘低精度模板
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
get_primes(a); // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘
for (int j = 0; j < sum[i]; j ++ )
res = mul(res, primes[i]);
卡特兰数
0表示向右走一格,1表示向上走一格。原题即从 $(0,0)$ 走到 $(n,n)$ ,同时只能在右下角,不经过左上角部分的走法。
不考虑限制的总走法为 $C_{2n}^{n}$ ,考虑对称线 $y=x+1$ ,所有到过左上角的路线,将其超出部分沿对称线翻转,其终点都会由 $(n,n)$ 变为 $(n-1,n+1)$ ,即我们需要减去的限制数量为 $C_{2n}^{n-1}$
卡特兰数
$$ C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n-1}}{n} $$
容斥原理
公式
$$ \left| S_1\cup S_2\cup \cdots \cup S_n \right|\\=\left( -1 \right) ^0\left| S_i \right|+\left( -1 \right) ^1\left| S_i\cap S_j \right|+\\\left( -1 \right) ^2\left| S_i\cap S_j\cap S_k \right|+\cdots +\left( -1 \right) ^{n-1}\left| S_1\cap S_2\cap \cdots \cap S_n \right| $$
技巧:从n个数的集合中选任意个数的子集,采用位运算的方式,利用二项式定理
for(int i=1;i<1<<n;i++){
for(int j=0;j<n;j++){
if(i>>j&1){
//具体操作
}
}
}
//时间复杂度:n*2^n
博弈论
普通NIM游戏:k-NIM游戏简单版
给定N堆物品,第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取。取走最后一件物品者获胜。两人都采取最优策略,问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手,第二个行动的称为后手。若在某一局面下无论采取何种行动,都会输掉游戏,则称该局面必败。
所谓采取最优策略是指,若在某一局面下存在某种行动,使得行动后对面面临必败局面,则优先采取该行动。同时,这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况,即两人均无失误,都采取最优策略行动时游戏的结果。
NIM博弈不存在平局,只有先手必胜和先手必败两种情况。
定理:
NIM博弈先手必胜,当且仅当 $A_1\land A_2\land \cdots \land A_n\ne 0$
证明:
- 若全为0,则必败
- 若不为0,$A_1\land A_2\land \cdots \land A_n=x\ne 0$ ,设 $x$ 的二进制表示中最高位为 $k$ ,则 $A_1$ 到 $A_n$ 中必然存在一个数 $A_i$ ,其第 $k$ 位是1。则 $A_i\land x<A_i$ ,令 $t=A_i-A_i\land x>0$ ,所以从 $A_i$ 拿走 $t$ 个后,$A_i$ 还剩 $A_i\land x$ 个。$A_1\land A_2\land \cdots \land A_n=x\land x=0$ ,
- 所以只需每次按照上述策略,就能使得后手一直为必败态,故先手必胜
公平组合游戏ICG
若一个游戏满足:
- 由两名玩家交替行动;
- 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;
- 不能行动的玩家判负;
则称该游戏为一个公平组合游戏
NIM博弈属于公平组合游戏,但常见的棋类游戏,比如围棋,就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和条件3
有向图游戏
给定一个有向无环图,图中有一个唯一的起点,在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。
具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行为能够到达的下一个局面连有向边。
Mex运算
设 $S$ 表示一个非负整数集合,定义 $\text{mex}\left( S \right)$ 为求出不属于集合 $S$ 的最小非负整数的运算,即:
$$
\text{mex}\left( S \right) =\min \left( x \right)
$$
$x$ 属于自然数,且 $x$ 不属于 $S$
SG函数
在有向图游戏中,对于每个节点 $x$ ,设从 $x$ 出发共有 $k$ 条有向边,分别到达节点 $y_1,y_2,…,y_k$ ,定义 $\text{SG}\left( x \right)$ 为 $x$ 的后继节点 $y_1,y_2,…,y_k$ 的SG函数值构成的集合再执行 $\text{mex}\left( S \right)$ 运算的结果,即:
$$
\text{SG}\left( x \right) =\text{mex}\left( \left\{ \text{SG}\left( y_1 \right) ,\text{SG}\left( y_2 \right) ,\cdots ,\text{SG}\left( y_k \right) \right\} \right)
$$
特别地,整个有向图游戏 $G$ 的 $\text{SG}$ 函数值被定义为有向图游戏起点 $s$ 的 $\text{SG}$ 函数值,即 $\text{SG}\left( G \right) =\text{SG}\left( s \right)$
有向图游戏的和
设 $G_1,G_2,\cdots ,G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$ ,它的行动规则是任选某个有向图游戏 $G_i$ ,并在 $G_i$ 上行动一步。$G$ 被称为有向图游戏 $G_1,G_2,\cdots ,G_m$ 的和。
有向图游戏的和的 $\text{SG}$ 函数值等于它包含的各个子游戏 $\text{SG}$ 函数值的异或值,即
$$
\text{SG}\left( G \right) =\text{SG}\left( G_1 \right) \land \text{SG}\left( G_2 \right) \land \cdots \land \text{SG}\left( G_m \right)
$$
定理:
有向图游戏某个局面必胜,当且仅当该局面对应节点的 $\text{SG}$ 函数值大于0
有向图游戏某个局面必败,当且仅当该局面对应节点的 $\text{SG}$ 函数值等于0
模板:求SG函数值
int S[N],F[M];//S集合包含n个每次可以拿取的石子个数
//F集合包含初始值为i的SG函数值(范围最大为M)
int sg(int x){
if(F[x] !=-1)return F[x];
unordered_set<int> Set;
//根据具体题目要求写
for(int i=0;i<n;i++){
if(x>=S[i])Set.insert(sg(x-S[i]));
}
//mex操作,找到最小的不属于集合的自然数
for(int i=0;;i++){
if(!Set.count(i))//找到不存在的最小自然数
return F[x]=i;
}
}
//初始化
memset(F,-1,sizeof F);