基础数学算法-有趣的数列

题目-有趣的数列

问题分析

尝试将偶数项作为横坐标, 奇数项作为纵坐标
因为要求$a_{2i-1}<a_{2i}$, 也就是说选法一定在$y=x$直线下方

相当于终点是$(n,n)$, 求合法的路径的数量, 就是$Catalan$序列

算法步骤

实现$C_{2n}^n-C_{2n}^{n-1}$对$P$取模的结果即可
因为$P\le 10^9$不能用$lucas$定理, 但是发现$n\le 10^6$, 尝试用快速幂求逆元的方式计算组合数, 但是发现$P$不一定是质数, 不能用费马小定理求解

求解该方程
$$x\cdot t\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}P)$$
尝试用扩展欧几里得算法计算, 但是前提是$x,P$互质, 才能用$exgcd$算法求解, 还是不行

代码实现

忽略了$x,P$互质情况的错误代码

快速幂求逆元的前提是$P$是质数, 扩展欧几里得算法求逆元的前提条件是$x,P$互质!!!

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e6 + 10;

int n, P;
LL fact[N], infact[N];

LL exgcd(LL a, LL b, LL &x, LL &y) {
   
    if (!b) {
   
        x = 1, y = 0;
        return a;
    }

    LL _x, _y;
    LL d = exgcd(b, a % b, _x, _y);
    x = _y, y = x - (a / b) * _y;
    return d;
}

void init(LL n) {
   
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= n; ++i) {
   
        fact[i] = fact[i - 1] % P * i % P;
        LL x, y;
        exgcd(fact[i] % P, P, x, y);
        infact[i] = x;
    }
}

LL C(int a, int b) {
   
    if (b < 0 || a < b) return 0;
    LL ans = fact[a] % P * infact[b] % P * infact[a - b] % P;
    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> P;

    init(2 * n);
    LL ans = C(2 * n, n) - C(2 * n, n - 1);
    ans = (ans % P + P) % P;

    cout << ans << '\n';
    return 0;
}

阶乘分解法求组合数, 注意每次计算组合数的时候清空$map$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e6 + 10;

int n, P;
int primes[N], cnt;
bool st[N];
map<int, int> mp;

void init(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[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void div(LL a, bool flag) {
   
    for (int i = 0; i < cnt; ++i) {
   
        int p = primes[i], t = 0;
        for (LL j = a; j; j /= p) t += j / p;
        if (t == 0) continue;
        flag ? mp[p] += t : mp[p] -= t;
    }
}

LL C(LL a, LL b) {
   
    mp.clear();
    if (b < 0 || a < b) return false;
    div(a, true), div(b, false), div(a - b, false);

    LL ans = 1;
    for (int i = 0; i < cnt; ++i) {
   
        int p = primes[i];
        for (int i = 0; i < mp[p]; ++i) ans = ans * p % P;
    }

    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init(N - 1);
    cin >> n >> P;

    LL ans = C(2 * n, n) - C(2 * n, n - 1);
    ans = (ans % P + P) % P;

    cout << ans << '\n';
    return 0;
}

快速幂优化阶乘分解代码, 注意每次乘法都要进行取模操作

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2e6 + 10;

int n, P;
int primes[N], cnt;
bool st[N];
map<int, int> mp;

void init(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[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void div(LL a, bool flag) {
   
    for (int i = 0; i < cnt; ++i) {
   
        int p = primes[i], t = 0;
        for (LL j = a; j; j /= p) t += j / p;
        if (t == 0) continue;
        flag ? mp[p] += t : mp[p] -= t;
    }
}

LL q_pow(LL a, LL b, int mod) {
   
    LL ans = 1;
    a %= mod;
    while (b) {
   
        if (b & 1) ans = ans % mod * a % mod;
        a = a % mod * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

LL C(LL a, LL b) {
   
    mp.clear();
    if (b < 0 || a < b) return false;
    div(a, true), div(b, false), div(a - b, false);

    LL ans = 1;
    for (int i = 0; i < cnt; ++i) {
   
        int p = primes[i];
        ans = ans % P * q_pow(p, (LL) mp[p], P);
    }

    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init(N - 1);
    cin >> n >> P;

    LL ans = C(2 * n, n) - C(2 * n, n - 1);
    ans = (ans % P + P) % P;

    cout << ans << '\n';
    return 0;
}