保研机试训练Day-22

数论

卡特兰数

给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

输出的答案对 10^9+7 取模。

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int mod =  1e9+7;

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

int main(){
    int n;
    cin >> n;
    int a = 2 * n, b = n;
    int res = 1;
  
    for(int i = a; i > a - b; i--) res = (ll)res * i % mod;
    for(int i=1;i<=b;i++) res = (ll)res * qmi(i, mod - 2, mod) % mod;
  
    res = (ll)res * qmi(n + 1, mod - 2, mod) % mod;
    cout << res << endl;
    return 0;
  
}

组合数学

容斥原理

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 20;
int n,m;
int p[N];

int main(){
    cin >> n >> m;
    int res = 0;
  
    for(int i = 0; i < m; i++) cin >> p[i];
  
    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;
}

博弈论

Nim游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}

台阶-Nim游戏

现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int res = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(i % 2) res ^= x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

集合-Nim游戏

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。