算法基础课-数学知识

质数

题目链接：866. 试除法判定质数 - AcWing题库
思路：1不是质数，枚举到根号n。

#include<bits/stdc++.h>

using namespace std;

bool check(int num){
    if(num == 1) return false;
    for(int i=2;i<=num/i;i++){
        if(num%i==0) return false;
    }
    return true;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        if(check(num)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    
    return 0;
}

题目链接：867. 分解质因数 - AcWing题库
思路：如下。G07 分解质因数 唯一分解定理 试除法_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
void process(int num){
    
    for(int i=2;i<=num/i;i++){
        int cnt = 0;
        while(num%i==0){
            num/=i;
            cnt++;
        }
        if(cnt) cout<<i<<" "<<cnt<<endl;
    }
    if(num>1) cout<<num<<" "<<1<<endl;
    
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        process(num);
        cout<<endl;
    }
    
    return 0;
}

题目链接：868. 筛质数 - AcWing题库
思路：G08 筛质数 埃氏筛法 线性筛法_哔哩哔哩_bilibili

埃氏筛法，从2开始筛到目标数字n。当前数字若不是合数（使用st数组判断），则一定是质数，将其加入到质数数组中(p数组，并使用cnt计数)。若为质数时，使用当前质数干掉后面的合数（从质数的平方开始枚举）。总体时间复杂度为O(nloglogn)。

线性筛法，埃氏筛法中每个合数有可能被不同的质数筛掉。线性筛保证每个合数均被其最小的质因子筛除，从而保证所有的数字只被记录一次，时间复杂度降低为O(n)。实际情况中的时间优化并不明显。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6+10;
int p[N];
int cnt;
int n;
bool st[N];
// void prime(){
//     for(int i=2;i<=n;i++){
//         if(!st[i]) p[++cnt] = i;
//         for(int j=1;1ll*i*p[j]<=n;j++){
//             st[i*p[j]] = true;
//             if(i%p[j] == 0) break;
//         }
//     }
// }
void prime(){
    for(ll i=2;i<=n;i++){
        if(!st[i]){
            p[++cnt] = i;
            for(ll j=i*i;j<=n;j+=i){
                st[j] = true;
            }
        }
    }
}

int main(){
    cin>>n;
    prime();
    // for(int i=1;i<=cnt;i++) cout<<p[i]<<" ";
    // cout<<endl;
    cout<<cnt<<endl;
    return 0;
}

约数

题目链接：869. 试除法求约数 - AcWing题库
思路：需要注意的地方在于对于像4,9,25这样可以正好开方的数，对于其约数只需输出一个。

#include<bits/stdc++.h>

using namespace std;

stack<int> stk;
int main(){
    int n;
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        for(int i=1;i<=num/i;i++){
            if(num%i==0){
                cout<<i<<" ";
                if(!(i*i == num))
                    stk.push(num/i);
            }
        }
        while(stk.size()){
            cout<<stk.top()<<" ";
            stk.pop();
        }
        cout<<endl;
    }
    
    
    return 0;
}

题目链接：870. 约数个数 - AcWing题库
思路：对输入的数分解质因数，并且记录在map中，最后统一处理。

约数个数如何求取？例如求360的约数个数，先进行因式分解。360可以由2^3*3^2*5^1得到。

那么他的约数可以从2中取值(0,1,2,3)，乘从3中取值(0,1,2)，乘从5中取值(0,1)得到。例如取2^0*3^0*5^0是1,1是360的约数。所以约数总的个数就是2的取值个数乘3的取值个数乘5的取值个数。

约数之和如何求取？同样的道理，也是从质因数中找数相乘，乘出来的结果一定是约数。将其相加即可。公式推导：约数和定理，约数个数定理_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int N = 110,mod = 1e9+7;
// int p[N];
int n;
unordered_map<int,int> p;

int main(){
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        //分解质因数
        for(int i=2;i<=num/i;i++){
            while(num%i==0){
                num/=i;
                p[i]++;
            }
        }
        if(num>1) p[num]++;
    }
    long long res = 1;
    for(auto t : p){
        res = res * (t.second + 1) % mod;
    }
    cout<<res<<endl;
    return 0;
}

题目链接：871. 约数之和 - AcWing题库
思路：需要注意的是代码while (b -- ) t = (t * a + 1) % mod;，跟字符串哈希有相似之处。

#include<bits/stdc++.h>

using namespace std;
const int N = 110,mod = 1e9+7;
// int p[N];
int n;
unordered_map<int,int> p;

int main(){
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        //分解质因数
        for(int i=2;i<=num/i;i++){
            while(num%i==0){
                num/=i;
                p[i]++;
            }
        }
        if(num>1) p[num]++;
    }
    long long res = 1;
    for(auto t : p){
        int num = t.first;
        int cnt = t.second;
        long long a = 1;
        while(cnt--){
            a = (a * num + 1) % mod;
        }
        res = res * a % mod;
    }
    cout<<res<<endl;
    return 0;
}

题目链接：872. 最大公约数 - AcWing题库
思路：G05 最大公约数 欧几里得算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b){
    if(b == 0) return a;
    return gcd(b,a%b);
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

欧拉函数

题目链接：873. 欧拉函数 - AcWing题库
思路：欧拉函数表示1-n中与n互质数字的个数。互质就是两个数的最大公约数是1。

解释一下phi(p^k)，表示p^(k-1)个循环节，每个循环节中有p-1个数与当前数字互斥。

#include<bits/stdc++.h>

using namespace std;

long long phi(int n){
    long long res = n;
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            res = res * (i-1)/i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res = res*(n-1)/n;
    return res;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int num;
        cin>>num;
        
        cout<<phi(num)<<endl;
    }
    return 0;
}

题目链接：874. 筛法求欧拉函数 - AcWing题库
思路：G09 筛法求欧拉函数_哔哩哔哩_bilibili

解释一下为什么i能被p[j]整除,则i包含m（i*p[j]）的所有质因子。

参考这篇题解AcWing 874. $\Huge\color{gold}{筛法求欧拉函数}$ - AcWing，如下图所示。由于i与m就相差个p[j]，i由m除p[j]得到，所以将i和m分解质因数后可以看出来，i仅在p[j]这个数的次数上相较于m差1，所以说i包含m的所有质因子。

解释一下为什么i不能被p[j]整除的情况下，i与p[j]互质。

因为p[j]是质数，其约数只有1和自身，i不能整除p[j]，所以对于i和p[j]来说的最大公约数只有1，所以互质。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+10;
int phi[N],vis[N];
int prime[N],cnt;

void get_phi(int n){
    phi[1] = 1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            prime[++cnt] = i;
            phi[i] = i-1;
        }
        for(int j=1;i*prime[j]<=n;j++){
            int m = i*prime[j];
            vis[m] = 1;
            if(i%prime[j] == 0){
                phi[m] = prime[j]*phi[i];
                break;
            }
            else phi[m] = (prime[j]-1)*phi[i];
        }
    }
}

int main(){
    int n;
    cin>>n;
    get_phi(n);
    long long sum = 0;
    for(int i=1;i<=n;i++){
        sum+=phi[i];
    }
    cout<<sum<<endl;
    return 0;
}

快速幂

题目链接：875. 快速幂 - AcWing题库

思路：G01 快速幂_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
LL quickpow(LL a,LL b,LL p){
    LL res = 1;
    while(b){
        if(b&1) res = res * a %p;
        a = a*a%p;
        b>>=1;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        LL a,b,p;
        cin>>a>>b>>p;
        cout<<quickpow(a,b,p)<<endl;
    }
    return 0;
}

题目链接：876. 快速幂求逆元 - AcWing题库
思路：G13 同余式 乘法逆元 费马小定理_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll quick_pow(ll a,ll n,int p){
    ll res = 1;
    while(n){
        if(n&1) res = res * a % p;
        a = a * a % p;
        n>>=1;
    }
    return res;
}


int main(){
    int n;
    cin>>n;
    while(n--){
        ll a,p;
        cin>>a>>p;
        if(a%p) cout<<quick_pow(a,p-2,p)<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}

扩展欧几里得算法

题目链接：877. 扩展欧几里得算法 - AcWing题库
思路：G17 不定方程 扩展欧几里得算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;

int extra_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x = 1; y = 0;
        return a;
    }
    int x1,y1;
    int d = extra_gcd(b,a%b,x1,y1);
    x = y1; y = x1 - a/b*y1;
    return d;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b,p;
        cin>>a>>b;
        int x,y;
        extra_gcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    
    return 0;
}

题目链接：876. 快速幂求逆元 - AcWing题库
思路：使用扩展欧几里得算法求逆元更加通用，快速幂求逆元要求a与p互质，且p为质数。但使用扩展欧几里得算法求逆元只要求a与p互质，不要求p一定为质数。具体思路是将同余式转化为不定方程求解。G18 同余方程 乘法逆元 扩展欧几里得算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
// ll quick_pow(ll a,ll n,int p){
//     ll res = 1;
//     while(n){
//         if(n&1) res = res * a % p;
//         a = a * a % p;
//         n>>=1;
//     }
//     return res;
// }
ll extra_gcd(ll a,ll b,ll &x, ll &y){
    if(b==0){
        x = 1;y=0;
        return a;
    }
    ll x1,y1,d;
    d = extra_gcd(b,a%b,x1,y1);
    x = y1;y = x1-a/b*y1;
    return d;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        ll a,p;
        ll x,y;
        cin>>a>>p;
        extra_gcd(a,p,x,y);
        if(a%p) cout<<(x%p+p)%p<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}

题目链接：878. 线性同余方程 - AcWing题库
思路：转化为不定方程求解。G18 同余方程 乘法逆元 扩展欧几里得算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll extra_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x = 1; y = 0;
        return a;
    }
    ll x1,y1;
    ll d = extra_gcd(b,a%b,x1,y1);
    x = y1; y = x1-a/b*y1;
    return d;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        ll a,b,m,x,y;
        cin>>a>>b>>m;
        ll d = extra_gcd(a,m,x,y);
        if(b%d==0){
            printf("%lld\n",1ll*b/d*x%m);
        }else cout<<"impossible"<<endl;
    }
    
    return 0;
}

中国剩余定理

题目链接：204. 表达整数的奇怪方式 - AcWing题库
思路：普通的中国剩余定理要求不同的同余方程之间的模互质，扩展中国剩余定理不要求模互质。

G19 中国剩余定理_哔哩哔哩_bilibili

G20 扩展中国剩余定理_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 30;
ll a[30],m[30];
int n;

ll extra_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x = 1;y = 0;
        return a;
    }
    ll x1,y1,d;
    d = extra_gcd(b,a%b,x1,y1);
    x = y1; y = x1 - a/b*y1;
    return d;
}

ll CRT(ll m[],ll r[]){
    ll m1,m2,r1,r2,p,q;
    m1 = m[1],r1 = r[1];
    for(int i=2;i<=n;i++){
        m2 = m[i];r2 = r[i];
        ll d = extra_gcd(m1,m2,p,q);
        if((r2-r1)%d) return -1;
        p = p*(r2-r1)/d;
        p = (p%(m2/d)+m2/d)%(m2/d);
        r1 = m1*p+r1;
        m1 = m1*m2/d;
    }
    return (r1%m1+m1)%m1;
}


int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>m[i];
    }
    cout<<CRT(a,m)<<endl;
    return 0;
}

高斯消元

题目链接：883. 高斯消元解线性方程组 - AcWing题库
思路：G23 线性方程组 高斯消元法_哔哩哔哩_bilibili

高斯消元法较为繁琐，思路如下图：

高斯-约旦消元法思路较为简单，主要思路是每轮循环，主元所在行不变，主元所在列消成0，如下图：

解的情况如下：

#include<bits/stdc++.h>

using namespace std;
const int N = 110;
const double eps = 1e-6;
double a[N][N];
int n;

int gauss(){

    for(int i=1;i<=n;i++){
        int r = i;
        for(int j=i;j<=n;j++){
            if(fabs(a[j][i])>eps){
                r = j;
                break;
            }
        }
        if(r!=i) swap(a[i],a[r]);
        
        if(fabs(a[i][i])<eps){
            continue;
        }
        
        for(int j=n+1;j>=i;j--){
            a[i][j] = a[i][j] / a[i][i];
        }
        
        for(int j=i+1;j<=n;j++){
            if(a[j][i]!=0){
                for(int k=n+1;k>=i;k--){
                    a[j][k] -= a[j][i]/a[i][i] *a[i][k];
                }
            }
        }
    }
    
    for(int i=n-1;i>=1;i--){
        for(int j=i+1;j<=n;j++){
            a[i][n+1] -= a[i][j] * a[j][n+1];
        }
    }
    
    for(int i=1;i<=n;i++){
        if(fabs(a[i][i])<eps){
           if(fabs(a[i][n+1])<eps) return 0; //无数解
            else return 1;  //无解 
        }
    }
    
    return 2;
}

int Gauss_Jordan(){
    
    for(int i=1;i<=n;i++){
        int r = i;
        for(int j=i;j<=n;j++){
            if(fabs(a[j][i])>eps){
                r = j;
                break;
            }
        }
        if(r!=i) swap(a[i],a[r]);
        
        if(fabs(a[i][i])<eps){
            continue;
        }
        
        for(int k=1;k<=n;k++){
            if(k == i) continue;
            double t = a[k][i]/a[i][i];
            for(int j=i;j<=n+1;j++){
                a[k][j] -= t*a[i][j];
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        if(fabs(a[i][i])<eps) continue;
        a[i][n+1] /= a[i][i];
    }

    for(int i=1;i<=n;i++){
        if(fabs(a[i][i])<eps){
           if(fabs(a[i][n+1])<eps) return 0; //无数解
            else return 1;  //无解 
        }
    }
    
    return 2;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+1;j++){
            cin>>a[i][j];
        }
    }
    // int rtn = gauss();
    int rtn = Gauss_Jordan();
    if(rtn == 2){
        for(int i=1;i<=n;i++) printf("%.2f\n",a[i][n+1]);
    }else if(rtn == 1) cout<<"No solution"<<endl;
    else cout<<"Infinite group solutions"<<endl;
    return 0;
}

组合计数

题目链接：885. 求组合数 I - AcWing题库
思路：递推G25 求组合数 递推法 杨辉三角_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int mod = 1e9+7;
const int N = 2010;
int c[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(j==0) c[i][j] = 1;
            else c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod;
        }
    }
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}

题目链接：AcWing 886. 求组合数 II - AcWing
思路：由于题目数据范围过大，递推法会TLE，可以考虑使用公式法求解，模意义下的组合数不能为小数，分数可以表示为逆元的形式。如何求逆元请看上面快速幂中求逆元的方法，当模数为质数时且ax\equiv1(mod p)中a与p互质（本题中p为很大的质数，a为较小的数，所以a与p一定互质），x表示a的逆元，由费马小定理可得x为a^(p-2)。可以直接用快速幂求取。G26 求组合数 快速幂_哔哩哔哩_bilibili

需要注意的是f数组和g数组要定义为long long类型的，不然可能输入的数据会溢出。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5+10,mod = 1e9+7;
ll f[N],g[N];

ll quick_pow(ll a,ll n){
    ll res = 1;
    while(n){
        if(n&1) res = res * a % mod;
        a = a * a % mod;
        n>>=1;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    f[0] = 1; g[0] = 1;
    for(int i=1;i<N;i++){
        f[i] = (ll)f[i-1] * i % mod;
        g[i] = (ll)quick_pow(i,mod-2) * g[i-1] % mod;
    }
    while(n--){
        
        ll a,b;
        cin>>a>>b;
        // cout<<f[a]<<" "<<g[a-b]<<" "<<g[b]<<endl;
        cout<<f[a] * g[a-b] % mod * g[b] % mod<<endl; 
    }
    
    return 0;
}

题目链接：887. 求组合数 III - AcWing题库

思路：当数字a,b远远大于质数p时，则不能保证a与p互质，所以费马小定理不再起作用。可以考虑将a%p映射到0-p-1，使得当前情况转化成上面的情况。G27 求组合数 卢卡斯定理_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100010;
ll f[N],g[N];

ll quick_pow(ll a,ll n, int p){
    ll res = 1;
    while(n){
        if(n&1) res = res * a % p;
        a = a * a % p;
        n>>=1;
    }
    return res;
}

void init(int p){
    f[0] = 1; g[0] = 1;
    for(int i=1;i<p;i++){
        f[i] = f[i-1] * i % p;
        g[i] = quick_pow(i,p-2,p) * g[i-1] % p;
    }
}

ll getC(ll n,ll m,int p){
    return f[n] * g[n-m] % p *g[m] % p;
}

ll Lucas(ll n,ll m,int p){
    if(n<p&&m<p) return getC(n,m,p);
    return Lucas(n/p,m/p,p) * getC(n%p,m%p,p) % p;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        ll a,b,p;
        cin>>a>>b>>p;
        init(p);
        printf("%lld\n",Lucas(a,b,p));
    }
    return 0;
}

题目链接：888. 求组合数 IV - AcWing题库
思路：G28 求组合数 高精度 线性筛_哔哩哔哩_bilibili

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 5010;
int prime[N],cnt;
bool st[N];
void init(){
    for(int i=2;i<N;i++){
        if(!st[i]){
            prime[++cnt] = i;
            for(int j=i*i;j<N;j=j+i){
                st[j] = true;
            }
        }
    }
}

ll get(int n,int p){
    ll s = 0;
    int a = p;
    while(n/p){
        s+=n/p;
        p*=a;
    }
    return s;
}

ll getC(int n,int m,int p){
    return get(n,p) - get(m,p) - get(n-m,p);
}

void mul(vector<int> &A,int p){
    vector<int> C;
    int t = 0;
    for(int i=0;i<A.size()||t;i++){
        if(i<A.size()) t += A[i]*p;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    A = C;
}

int main(){
    int n,m;
    cin>>n>>m;
    init();
    vector<int> C;
    C.push_back(1);
    for(int i=1;i<=cnt;i++){
        int p = prime[i];
        int s = getC(n,m,p);
        while(s--) mul(C,p);
    }
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl;
    return 0;
}

 题目链接：889. 满足条件的01序列 - AcWing题库

思路：卡特兰数。G32 卡特兰数_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int N = 200010,mod = 1e9+7;
typedef long long ll;
int n;
ll f[N],g[N];
ll qmi(ll a,ll n,int p){
    ll res = 1;
    while(n){
        if(n&1) res = res*a%p;
        a= a*a%p;
        n>>=1;
    }
    return res;
}

void init(int p){
    f[0] = 1;g[0] = 1;
    for(int i=1;i<=2*n+1;i++){
        f[i] = f[i-1] * i %p;
        g[i] = qmi(i,p-2,p) * g[i-1] % p;
    }
}

ll getC(int n,int m,int p){
    return f[n] *g[n-m] %p *g[m]%p;
}

int main(){
    cin>>n;
    init(mod);
    cout<<(getC(2*n,n,mod) - getC(2*n,n-1,mod) + mod)%mod<<endl;
    return 0;
}

容斥原理

题目链接：890. 能被整除的数 - AcWing题库

思路：使用2进制位表示当前数字n是否能被每个质数整除。外层循环所有的状态，内层找到每一位G30 容斥原理 集合的并_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int M = 20;
int prim[M];
typedef long long ll;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>prim[i];
    int res = 0;
    for(int i=1;i<1<<m;i++){
        int t = 1,sign = -1;
        for(int j=0;j<m;j++){
            if(i&1<<j){
                if((ll)t*prim[j]>n){
                    t = 0;
                    break;
                }
                sign = -sign;
                t*=prim[j];
            }
        }
        if(t) res = res + n/t*sign;
    }
    cout<<res<<endl;
    return 0;
}

简单博弈论

题目链接：891. Nim游戏 - AcWing题库
思路：G58 尼姆（Nim）游戏【博弈论】_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    int res = 0;
    while(n--){
        int num;
        cin>>num;
        res^=num;
    }
    if(res == 0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

题目链接：892. 台阶-Nim游戏 - AcWing题库
思路：G59 台阶型 Nim游戏【博弈论】_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];

int main(){
    int n;
    cin>>n;
    int res = 0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i%2) res^=a[i];
    }
    if(res == 0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

题目链接：893. 集合-Nim游戏 - AcWing题库

思路：G60 有向图游戏 SG函数【博弈论】_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
int k,n;
int f[100010];
int a[110];
int sg(int x){
    if(f[x]!=-1) return f[x];
    set<int> S;
    
    for(int i=0;i<k;i++){
        if(x>=a[i]){
            S.insert(sg(x-a[i]));
        }
    }
    for(int i=0;;i++)
        if(!S.count(i))
            return f[x] = i;
    
}


int main(){
    memset(f,-1,sizeof f);
    cin>>k;
    for(int i=0;i<k;i++) cin>>a[i];
    cin>>n;
    int res = 0;
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        // cout<<sg(num)<<endl;
        res^=sg(num);
    }
    if(res == 0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/370642.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

用c语言实现三子棋

用c语言实现三子棋

首先创建三个文本框&#xff1a;game.h&#xff08;放在头文件内&#xff09;test.c game.c&#xff08;放在源文件中&#xff09; 首先进行框架的搭建&#xff08;放在test.c文件中&#xff09; game.h #pragma once #define ROW 3 #define COL 3 void InitBoard(char board…
阅读更多...
ChatGPT生产力|chat gpt实战介绍

ChatGPT生产力|chat gpt实战介绍

标注说| ⭐ : 使用稳定&#xff0c;推荐 | &#x1f604; : 免费使用 | &#x1f511; : 需要登陆或密码 | ✈️ : 需waiwang进行访问 | ChatGPT 1PoePoe - Fast, Helpful ...&#x1f511;&#x1f604;&#x1f517;2 AItianhuGPT4&#x1f604;⭐&#x1f517;3 PhantoNa…
阅读更多...
14：中断

14：中断

中断 1、中断的引入2、使用单片机外部中断来处理按键2.1、外部中断2.2、参考数据手册中示例代码写程序2.2.1、外部中断0的测试程序2.2.2、完整程序 1、中断的引入 任务&#xff1a;独立数码管循环显示0-9&#xff0c;同时按键控制LED1亮灭。 代码如下&#xff1a; #include …
阅读更多...
[word] word页面视图放大后，影响打印吗？ #笔记#学习方法

[word] word页面视图放大后，影响打印吗？ #笔记#学习方法

word页面视图放大后&#xff0c;影响打印吗&#xff1f; word文档的页面视图又叫普通视图&#xff0c;又叫打印视图&#xff0c;是系统默认的视图&#xff0c;是用户用的最多最常见的视图。 问&#xff1a;怎样打开页面视图&#xff1f; 答&#xff1a;两种方法 方法一、点…
阅读更多...
彻底扒光QQ音乐，批量下载音乐和MV文件

彻底扒光QQ音乐，批量下载音乐和MV文件

购买了一年的QQ音乐绿钻豪华版&#xff0c;还有几天就到期了&#xff0c;虽然平时听音乐比较少&#xff0c;但是还比较喜欢听歌曲的。计划会员到期前下载一些音乐文件&#xff0c;继续针对QQ音乐网站源码分析和歌曲下载链接的进行研究。 平时通过APP和软件播放歌曲也是趋势&…
阅读更多...
2024年最新幻兽帕鲁服务器搭建教程

2024年最新幻兽帕鲁服务器搭建教程

玩转幻兽帕鲁服务器&#xff0c;阿里云推出新手0基础一键部署幻兽帕鲁服务器教程&#xff0c;傻瓜式一键部署&#xff0c;3分钟即可成功创建一台Palworld专属服务器&#xff0c;成本仅需26元&#xff0c;阿里云服务器网aliyunfuwuqi.com分享2024年新版基于阿里云搭建幻兽帕鲁服…
阅读更多...
【JavaEE进阶】 图书管理系统开发日记——伍

【JavaEE进阶】 图书管理系统开发日记——伍

文章目录 &#x1f38b;前言&#x1f332;需求分析&#x1f384;约定前后端交互接口&#x1f333;实现服务器代码&#x1f6a9;控制层&#x1f6a9;业务层&#x1f6a9;数据层 &#x1f343;修改前端代码⭕总结 &#x1f38b;前言 这次我们来实现图书管理系统的增加图书模块。…
阅读更多...
船舶监造系统：从设计到实现的全程解析

船舶监造系统：从设计到实现的全程解析

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…
阅读更多...
01-操作系统_名词_文件下载_反弹

01-操作系统_名词_文件下载_反弹

操作系统_名词_文件下载_反弹 一、渗透测试1.1、POC、EXP、Payload与Shellcode1.2、后门1.3、木马1.4、反弹1.5、回显1.6、跳板1.7、黑白盒测试1.8、暴力破解1.9、社会工程学1.10、撞库1.11、ATT&CK 二、案例演示2.1、基础案例1&#xff1a;操作系统-用途&命令&权限…
阅读更多...
AI-数学-高中-22-tanx的图像与性质

AI-数学-高中-22-tanx的图像与性质

原作者视频&#xff1a;三角函数】9tanx的图像与性质&#xff08;易中档&#xff09;_哔哩哔哩_bilibili 做题时注意先画图&#xff0c;再计算。
阅读更多...
电脑显示mfc140u.dll丢失怎么修复，这几个方法都可以解决

电脑显示mfc140u.dll丢失怎么修复，这几个方法都可以解决

当打开软件时出现"mfc140u.dll丢失"的错误提示&#xff0c;通常是由于缺少或损坏了Microsoft Foundation Class (MFC)库文件导致的。MFC是Microsoft提供的一套用于开发Windows应用程序的类库&#xff0c;它包含了许多常用的功能和组件。 1、以下是可能导致"mfc…
阅读更多...
BFS——双向广搜+A—star

BFS——双向广搜+A—star

有时候从一个点能扩展出来的情况很多&#xff0c;这样几层之后搜索空间就很大了&#xff0c;我们采用从两端同时进行搜索的策略&#xff0c;压缩搜索空间。 190. 字串变换(190. 字串变换 - AcWing题库) 思路&#xff1a;这题因为变化规则很多&#xff0c;所以我们一层一层往外…
阅读更多...
Python实战：爬取小红书

Python实战：爬取小红书

有读者在公众号后台询问爬取小红书&#xff0c;今天他来了。 本文可以根据关键词&#xff0c;在小红书搜索相关笔记&#xff0c;并保存为excel表格。 爬取的字段包括笔记标题、作者、笔记链接、作者主页地址、作者头像、点赞量。 一、先看效果 1、爬取搜索页 2、爬取结果保存到…
阅读更多...
2-12 SDATR的训练与测试

2-12 SDATR的训练与测试

2.12 SDATR的训练与测试 使用环境：3卡服务器SDATR 服务器代码地址：/home/lihuanyu/code/036SDATR 本地代码地址：F:\BaiduNetdiskDownload\code\036SDATR 2.12.1 训练文件修改 输入数据修改 载入词汇修改 短点保存修改 权重保存修改 其他位置修改：
阅读更多...
docker搭建Mysql集群准备（一）

docker搭建Mysql集群准备（一）

docker搭建Mysql集群准备 Linux基本知识&#xff1a; 修改机器 IP&#xff0c;变成静态 IP vim /etc/sysconfig/network-scripts/ifcfg-ens33 文件 TYPEEthernet PROXY_METHODnone BROWSER_ONLYno BOOTPROTOstatic IPADDR192.168.190.67 NETMASK255.255.255.0 GAT…
阅读更多...
优秀学习网站推荐-第一辑

优秀学习网站推荐-第一辑

原文地址&#xff1a;https://jaune162.blog/2024/02/15/study-website-recommend Developer Roadmaps&#xff08;开发者路线图&#xff09; 官网地址&#xff1a;https://roadmap.sh/ 该网站包含了各个方向、各个语言的开发人员从零开始学习的路线图。 下图为Java方向的学…
阅读更多...
1997-2022年中央对各省份一般公共预算转移支付数据

1997-2022年中央对各省份一般公共预算转移支付数据

1997-2022年中央对各省份一般公共预算转移支付数据 1、时间&#xff1a;1997-2022年 2、范围&#xff1a;31省 3、指标&#xff1a;一般公共预算转移支付 4、来源&#xff1a;wind 财政部 5、指标解释&#xff1a;一般性转移支付又称体制性转移支付&#xff0c;是指上级政…
阅读更多...
回归预测 | Matlab基于OOA-LSSVM鱼鹰算法优化最小二乘支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于OOA-LSSVM鱼鹰算法优化最小二乘支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于OOA-LSSVM鱼鹰算法优化最小二乘支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab基于OOA-LSSVM鱼鹰算法优化最小二乘支持向量机的数据多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab基于OOA-LSSVM鱼鹰算法…
阅读更多...
Linux---进程间通信 | 管道 | PIPE | MKFIFO | 共享内存 | 消息队列

Linux---进程间通信 | 管道 | PIPE | MKFIFO | 共享内存 | 消息队列

管道 管道是UNIX中最古老的进程间通信的形式&#xff0c;我们把从一个进程连接到另一个进程的数据流称为一个管道。 一个文件&#xff0c;可以被多个进程打开吗&#xff1f;可以&#xff0c;那如果一个进程打开文件&#xff0c;往文件里面写数据&#xff0c;另一个进程打开文…
阅读更多...
SQL Server之DML触发器

SQL Server之DML触发器

一、如何创建一个触发器呢 触发器的定义语言如下&#xff1a; CREATE [ OR ALTER ] TRIGGER trigger_nameon {table_name | view_name}{for | After | Instead of }[ insert, update,delete ]assql_statement从这个定义语言我们可以知道如下信息&#xff1a; trigger_name&…
阅读更多...
最新文章

Copyright @ 2022~2023