初等数学知识总结

质数

试除法判断质数

bool is_prime(int n){
	if(n<2)return false;
	for(int i=2;i<=n/i;i++){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
1
2
3
4
5
6
7
8
9

求解质因子

void divide(int n){
	for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    }
    if(n>1)printf("%d %d\n",n,1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

筛法

埃氏筛 – 时间复杂度( O(nloglogn) )

跟朴素筛的区别在于减少了 合数的倍数搜索

const int N=1000010;
int prime[N],cnt;
bool st[N];
void get_prime(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			prime[cnt++]=i;
			for(int j=i+i;j<=n;j+=i)st[j]=true;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

线性筛

保证每个数只会被筛一次

所以是线性的

const int N=1000010;
int prime[N],cnt;
bool st[N];
void get_prime(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			prime[cnt++]=i;
		}
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

约数

n的约数个数求解：

​ 可参考求解质因子 程序
$$N=P_1^{a_1}\ast P_2^{a_2}\ast ...\ast P_n^{a_n}$$
答案：
$$(a_1+1)\ast (a_2+1)\ast (a_3+1)\ast ...\ast (a_n+1)$$

约数之和：

$$(P_1^0+P_1^1+...+P_1^{a_1})\ast ...\ast (P_k^0+...+P_k^{a_k})$$

最大公约数

d可整除a d可整除b 那么d可整除（x*a+y*b）

（a,b）的最大公约数 也是（b, a%b）的最大公约数
$$a\%b=a-c\ast bc=a/b;$$
欧几里得算法：时间复杂度：O(logn)

int gcd(a,b){
	return b?gcd(b,a%b):a;
}
1
2
3

欧拉函数

定义：f(N) 求解 1-n中与n互质的数的个数
$$N=P_1^{a_1}\ast P_2^{a_2}\ast ...\ast P_n^{a_n}$$

$$f(N)=N\ast (1-\frac{1}{P_1})(1-\frac{1}{P_2})(1-\frac{1}{P_3})....(1-\frac{1}{P_n})$$

上式可由容斥原理得到

//欧拉函数模板
#include 
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int t;
        scanf("%d",&t);
        int res=t;
        for(int j=2;j<=t/j;j++){
            if(t%j==0){
                while(t%j==0){
                    t/=j;
                }
                res=res/j*(j-1);
            }
        }
        if(t>1)res=res/t*(t-1);
        cout<<res<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//线性求欧拉函数
#include 
using namespace std;
typedef long long ll;
const int mx=1e6+10;
ll st[mx];//存储线性筛的结果
ll cnt=0;//记录线性筛的数量
bool f[mx];
ll phi[mx];//存储i的欧拉函数的值
ll er(int n){//求1-n的所有欧拉函数的和
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!f[i]){
            st[cnt++]=i;
            phi[i]=i-1;//质数的欧拉函数的值为i-1
        }
        for(int j=0;st[j]<=n/i;j++){
            f[st[j]*i]=true;
            if(i%st[j]==0){
                phi[i*st[j]]=st[j]*phi[i];//若质因子 早已存在，则只需改变原来的N即可
                break;
            }
            phi[i*st[j]]=phi[i]*(st[j]-1);//若质因子不存在，则不仅需要改变N还需要*(1-1/pj)
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=phi[i];//求和即可
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    cout<<er(n)<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

欧拉定理

若a与n互质，则$a^{\phi (n)}\equiv 1\%n$

证明 在1-n中 ，有$a_1......a_{\phi (n)}$，则有$a{a}_1.....a{a}_{\phi (n)}$

则 $a^{\phi (n)}(a_1.....a_{\phi (n)})\equiv a\mathrm{1.....}{a}_{\phi (n)}\%n$

$a^{\phi (n)}\equiv 1\%n$

费马定理

由欧拉定理得到：

a与n互质时，若n为质数，则$\phi (n)=n-1$

所以由由欧拉定理得到：$a^{n-1}\equiv 1\%n$

快速幂

//模板
#include
using namespace std;
typedef long long LL;//设计数论常用LL
LL qmi(int a,int k,int p){//a底数 k指数 p取余
    int res=1;
    while(k){
        if(k&1)res=(LL)res*a%p;//当k为奇数
        k>>=1;//k%2
        a=(LL)a*a%p;
    }
    return res;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a,k,p;
        scanf("%d%d%d",&a,&k,&p);
        cout<<qmi(a,k,p)<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

快速幂+费马求逆元

求a模p的逆，若p为质数，则利用费马定理可得，a的逆元 为
$$a^{p-2}\%p$$

扩展欧几里得

原理：在欧几里得（辗转相除）算法基础上计算

//欧几里得算法
void gcd(int a,int b){
    return b?gcd(b,a%b):a;
	//换句话说
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
1
2
3
4
5
6
7
8
9

任意a，b ，必然存在 x ,y 使得 ax+by=gcd(a,b);

当b为0时 ， x即为1 y即为0

by+(a%b)x$\equiv$gcd(a,b)

by+(a-a/b*b)x$\equiv$gcd(a,b)

ax+b(y-a/b*x)$\equiv$gcd(a,b)

即存在 x,y,x’,y’使得 ax+by$\equiv$gcd(a,b)

bx’+(a%b)y’$\equiv$bx’+(a-a/b*b)y’=ay’+b(x’-a/b*y’) $\equiv$gcd(a,b)

所以可得 ay’+b(x’-a/b*y’)$\equiv$ax+by$\equiv$gcd(a,b)

x=y’

y=(x’-a/b*y’);

我们需要通过拓欧求x,y 所以需要递归求y‘ x’

已知 a,b 扩展欧几里得求解 x,y

#include 
using namespace std;
int exgcd(int a,int b,int &x,int &y){//扩展欧几里得 x,y记得加引用&符号
    if(!b){//当b为0时，x一定为1 y一定为0
        x=1;
        y=0;
        return a;//最大公约数为此时的 a
    }
    int e=exgcd(b,a%b,y,x);
    
    y-=a/b*x;//求解此时x对应下的y
    return e;
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b;
        scanf("%d%d",&a,&b);
        int x,y;
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

扩展欧几里得求 $ax\equiv b(modm)$

存在一个y使得 ax = my + b ;

则 ax-my=b;

使得y’=-y

则 ax+my’=b; 有解前提 b可以整除 gcd (a , m)，否则 x无解

只需求解 x,y即可

线性同余方程

给定n组数据$a_i,b_i,m_i$,对于每组数 求出一个x，使其满足$a_i\ast x_i\equiv b_i$，如果无解 输出impossible

#include 
using namespace std;
typedef long long LL;
int exgcd(int a,int b,int &x,int &y){//扩欧
    if(!b){
        x=1;y=0;//当b为0时，a,b的最大公约数肯定为a，此时x为1
        return a;
    }
    int d=exgcd(b,a%b,y,x);//递归求解 x' y'
    y-=a/b*x;//通过x' y'求解y
    return d;//函数值依然返回最大公约数
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b,m;
        scanf("%d%d%d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d){//扩欧前提要求
            puts("impossible");
        }else{
            cout<<(LL)x*(b/d)%m<<endl;//注意取模 --题目要求
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

扩展欧几里得 求逆元

线性同余方程

$$ax\equiv 1(modm)$$

a模m的逆 有解前提 gcd ( a , m ) = 1 ；

中国剩余定理

存在$m_1...m_k$两两互斥
{ x ≡ a 1   ( m o d   m 1 ) x ≡ a 2   ( m o d   m 2 ) . . . . x ≡ a k   ( m o d   m k )

⎩ ⎨ ⎧​x≡a1 (mod m1​)x≡a2 (mod m2​)....x≡ak (mod mk​)​
求解x
$$M=m_1\ast m_2\ast ...\ast m_k$$

$$M_i=\frac{M}{m_i}$$

$M_i$（除mi之外所有m的乘积）与mi互质

$M_i^{-1}$表示Mi模mi的逆
$$x=a_1{M}_i{M}_i^{-1}+...+a_k{M}_k{M}_k^{-1}$$
证明：$M_i{M}_i^{-1}\%m_i=1$，所以$x\equiv a_i(mod{m}_i)$成立

此即为中国剩余定理：

$$x=a_1{M}_i{M}_i^{-1}+...+a_k{M}_k{M}_k^{-1}$$

例题acwing.204

对于每两个式子，我们考虑将其合并

$x\equiv m1(moda1)$

$x\equiv m2(moda2)$

则有：

$x=k_1\ast a_1+m_1$

$x=k_2\ast a_2+m_2$

进一步：

$a_1\ast k_1+m1=k_2\ast a_2+m_2$

移项：

$k_1\ast a_1-k_2\ast a_2=m_2-m_1$

用扩展欧几里得 求解k1,k2asfd f1

无解判断

若gcd(a1-a2)|m2-m1 则 有解

否则无解

我们只需要让k1扩大（m2-m1)/d倍即可

找到最小正整数解

$k1=k1+k\ast \frac{a_2}{d}$

$k2=k2+k\ast \frac{a_1}{d}$

带入原式仍满足

$k_1\ast a_1+k_2\ast a_2=m_2-m_1$

合并完成后：

$x=(k1+k\ast \frac{a2}{d})\ast a_1+m_1$

=$k1\ast a1+m1+k\ast lcm(a1,a2)$

此时的m1变为k1*a1

此时的a1 变为lcm(a1,a2)

#include 
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;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    int n;
    cin>>n;
    LL a1,m1;
    bool f=false;
    cin>>a1>>m1;
    for(int i=0;i<n-1;i++){
        LL a2,m2;
        cin>>a2>>m2;
        LL x,y;
        LL d=exgcd(a1,a2,x,y);
        if((m2-m1)%d){//判断是否有解
            f=1;
            break;
        }
        
        LL t= a2/d;
        x*=(m2-m1)/d;//x需要扩大倍数
        x=(x%t+t)%t;//需要找一个最小非负整数解。
        m1=x*a1+m1;//合并后方程的m1
        a1=abs(a1/d*a2);//合并后方程的a1;
    }
    if(f){
        cout<<-1<<endl;
    }
    else{
        cout<<(m1%a1+a1)%a1<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

高斯消元 gauss

方法：枚举每一列

1、找到绝对值最大的一行

2、将改行换到最上面

3、将改行的第一个数变为1

4、将改列下面的所有行的该列值都变为0

#include 
#include 
using namespace std;
int n;
const int maxn=110;
double a[maxn][maxn];
const double eps=1e-6;
void output(){//输出矩阵的情况
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
int gauss(){//高斯消元
    int r=0;int c=0;//r行数 c列数
    for(;c<n;c++){//遍历列数 从小往大遍历每一列
        int t=r;
        for(int i=r;i<n;i++){//找当前列最大值对应的行 然后将改行放到尽可能地最前面
            if(fabs(a[i][c])>fabs(a[t][c])){
                t=i;
            }
        }
        // output();
        if(fabs(a[t][c])<=eps)continue;//如果当前列全部为0,则无需操作了
        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++){
            for(int j=n;j>=c;j--){
                if(fabs(a[i][c])>eps)//将该列的其他值变为0,同时修改该行的其他值
                a[i][j]-=a[i][c]*a[r][j];
            }
        }
        r++;//这算一行有效行
        // output();
    }
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++){
            a[i][n]-=a[i][j]*a[j][n];//计算未知数的解
        }
    }
    if(r<n){
        for(int i=r;i<n;i++){
            if(fabs(a[i][n])>eps){//若改行的值不为0,则说明是 0==!0,所无解
                return 2;
            }
        }
        return 1;//否则有无穷多解
    }
    return 0;//唯一解
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cin>>a[i][j];
            // scanf("%lf",&a[i][j]);
            // cout<
        }
    }
    // output();
    int t=gauss();
    if(t==0){
        for(int i=0;i<n;i++){
            if(fabs(a[i][n])<eps)printf("0.00\n");
            else
            printf("%.2lf\n",a[i][n]);
        }
    }
    else if(t==2){
        printf("No solution\n");
    }else{
        printf("Infinite group solutions\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

组合数

方法一：递推 – 适合 询问次数10w次，a，b范围（1-2000）

$$C_a^b=\frac{a!}{b!(a-b)!}=C_{a-1}^b+C_{a-1}^{b-1}$$

#include 
using namespace std;
const int maxn=2010;
const int mod=1e9+7;
int c[maxn][maxn];
void init(){
    for(int i=0;i<maxn;i++){
        for(int j=0;j<=i;j++){
            if(j==0)c[i][j]=1;//若当前j为零，则结果为1
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;//地推公式
        }
    }
}
int main(){
    init();
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        cout<<c[a][b]<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：预处理

$$C_a^b=\frac{a!}{b!(a-b)!}=a!(b!{)}^{-1}((a-b)!{)}^{-1}$$

#include 
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1e5+10;
LL a[maxn],b[maxn];//a数组存储阶乘,b数组存储阶乘的逆
LL quick(int n,int m,int mod){//快速幂求解逆元
    LL res=1;
    while(m>0){
        if(m&1)res=(LL)res*n%mod;//快速幂 需要(LL)扩展
        m>>=1;
        n=(LL)n*n%mod;//需要(LL)扩展
    }
    return res;
}
int main(){
    a[0]=1;
    b[0]=1;
    for(int i=1;i<maxn;i++){
        a[i]=a[i-1]*i%mod;
        b[i]=b[i-1]*quick(i,mod-2,mod)%mod;//阶乘的逆 就等于(i-1)!的逆 *i的逆
    }
    int n;
    scanf("%d",&n);
    while(n--){
        int n1,n2;
        scanf("%d%d",&n1,&n2);
        printf("%lld\n",a[n1]*b[n2]%mod*b[n1-n2]%mod);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

方法三：卢卡斯定理 次数控制在20次，a b的范围在$(1-10^{18})$

$$C_a^b=C_{a\%p}^{b\%p}\ast C_{a/p}^{b/p}(modp)$$

#include 
using namespace std;
typedef long long LL;
LL a,b,p;
LL quick(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1)res=(LL)res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
LL C(LL a,LL b){//暴力求组合数
    LL res=1;
    for(LL i=1,j=a;i<=b;i++,j--){
        res=res*j%p;
        res=res*(quick(i,p-2))%p;//取逆元
    }
    return res;
}
LL lucas(LL a,LL b){//卢卡斯定理
    if(a<p&&b<p)return C(a%p,b%p)%p;
    else return (LL)C(a%p,b%p)%p*lucas(a/p,b/p)%p;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        scanf("%lld%lld%lld",&a,&b,&p);
        cout<<lucas(a,b)<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法四：高精度求解 a b取值范围($1-500$)，但是不允许取余

知识点：$a!$中质因子p的个数求解公式：
$$res=\frac{a}{p}+\frac{a}{p^2}+\frac{a}{p^3}+...+\frac{a}{p^n}$$

#include 
#include 
using namespace std;
const int maxn=1e5+10;
int prime[maxn];
bool f[maxn];
int cnt=0;
int sum[maxn];
void get_prime(int n){
    f[1]=1;
    for(int i=2;i<maxn;i++){
        if(!f[i])prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++){
            f[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int p;
int get(int i){
    int res=0;
    while(i){
        res+=i/p;
        i/=p;
    }
    return res;
}
vector<int> mul(vector<int>res,int a){//高精度乘法
    int t=0;
    vector<int>c;
    for(int i=0;i<res.size();i++){
        t+=res[i]*a;
        c.push_back(t%10);
        t/=10;
    }
    while(t){
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
int main(){
    get_prime(maxn);
    int a,b;
    scanf("%d%d",&a,&b);
    for(int i=0;i<cnt;i++){
        p=prime[i];
        sum[i]=get(a)-get(b)-get(a-b);//计算每个质数最终能剩有多少个值
    }
    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,prime[i]);//求解高精度
        }
    }
    for(int i=res.size()-1;i>=0;i--){//高精度输出
        cout<<res[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

卡特兰数

$$C$$

容斥原理

韦恩图 求圆的面积，所有圆的面积为 奇数个圆面积的交集 减去 偶数个圆面积的交集

[acwing–890](890. 能被整除的数 - AcWing题库)

题解：找到每个质因子所能整除的的数的集合，然后减去重合的部分，即可

可利用容斥原理，暴力所有情况（可通过位运算判断当前数取或者不取 快速完成位运算），如果该数包含偶数个质因子，则该数的倍数需要减去，如果该数包含奇数个质因子，则该数的所有倍数需要加上，最后求个数即可。

#include 
using namespace std;
typedef long long LL;
int main(){
    LL n,m;
    cin>>n>>m;
    LL p[20];
    for(int i=0;i<m;i++){
        scanf("%lld",&p[i]);
    }
    int sum=0;
    for(int i=1;i<1<<m;i++){
        LL t=1;
        LL cnt=0;
        for(int j=0;j<m;j++){
            if(i>>j&1){
                cnt++;
                t*=p[j];
                if(t>n){
                    t=-1;
                    break;
                }
            }
        }
        if(t!=-1){
            if(cnt&1)sum+=n/t;
            else sum-=n/t;
        }
    }
    cout<<sum<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

尼姆游戏

有n堆石子，两个人轮流从n堆石子中拿任意个石子，问能否获得胜利

结论：

若有$a_1,a_2,a_3...a_n$个石子，若$a_1\wedge a_2\wedge ...\wedge a_n==0$则一定后手必胜，否则先手必胜

证明：

1、0^0^0^0…^0=0

2、若$a_1\wedge a_2\wedge ...\wedge a_n\ne 0$，则假设$a_1\wedge a_2\wedge ...\wedge a_n=x$，下一步一定可以变为$a_1\wedge a_2\wedge ...\wedge a_n=0$

证明：若x的最高为1的位为k，则$a_1-a_k$中至少存在一个数的第k位二进制数为1，假设该数为$a_i$，则一定有$a_i\wedge x<a_i$，则每次只需要抽取$a_i-(a_i\wedge x)$个石子即可将$a_i$变为（$a_i\wedge x$）个石子，带回原式即可得到0

3、若$a_1\wedge a_2\wedge ...\wedge a_n=0$，则下一步无论怎么操作，都会使得$a_1\wedge a_2\wedge ...\wedge a_n\ne 0$

证明：反证法：
$$a_1\wedge a_2\wedge ...\wedge a_i\wedge a_{i+1}...\wedge a_n=0$$
​ 若将$a_i$变为$a_i^{\prime }$，即
$$a_1\wedge a_2\wedge ...\wedge a_i^{\prime }\wedge a_{i+1}...\wedge a_n=0$$
将方程37异或方程38

可得
$$a_i^{\prime }\wedge a_i=0$$
若成立，则$a_i^{\prime }=a_i$

由题意得，不成立，则若$a_1\wedge a_2\wedge ...\wedge a_n=0$，则下一步无论怎么操作，都会使得$a_1\wedge a_2\wedge ...\wedge a_n\ne 0$

SG函数

Mex运算

设S表示一个非负整数集合，定义mex(S)为求出不属于集合S的最小非负整数运算，即：mex（S）=min{x};

例如：S={0，1，2，4}，那么mex(S)=3;

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1,y2,…yk，定义SG(x)的后记节点为y1,y2…

yk的SG函数值构成的集合在执行mex运算得出的结果，即：

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)xorSG(G2)xor…xorSG(Gm)

[acwing.893 集合Nim游戏](893. 集合-Nim游戏 - AcWing题库)

#include 
#include 
#include 
using namespace std;
int s[200];
int f[10005];
int n;
int sg(int x){
    if(f[x]!=-1)return f[x];
    unordered_set<int>mp;
    for(int i=0;i<n;i++){
        int t;
        if(x>=s[i]){
            mp.insert(sg(x-s[i]));
        }
    }
    for(int i=0;;i++){
        if(!mp.count(i)){
            f[x]=i;
            return i;
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<10005;i++){
        f[i]=-1;
    }
    int m;
    cin>>m;
    int res=0;
    for(int i=0;i<m;i++){
        int t;
        cin>>t;
        res^=sg(t);
    }
    if(res==0)printf("No\n");
    else printf("Yes\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42