容斥原理 与 卡特兰数

// 通用骨架：求 |A1 ∪ A2 ∪ ... ∪ An|
long long inclusionExclusion(int n) {
    long long ans = 0;
    for (int S = 1; S < (1 << n); S++) {          // 枚举所有非空子集
        long long cnt = /* |∩_{i∈S} A_i| 的计算 */ 0;
        int bits = __builtin_popcount(S);            // 子集大小
        if (bits & 1) ans += cnt;                      // 奇数加
        else       ans -= cnt;                      // 偶数减
    }
    return ans;
}

// 具体例：1~N 中能被 a1..an 中至少一个整除的数的个数
long long countDivisible(long long N, vector<long long>& a) {
    int n = a.size();
    long long ans = 0;
    for (int S = 1; S < (1 << n); S++) {
        long long l = 1; bool ok = true;
        for (int i = 0; i < n; i++)
            if (S >> i & 1) {
                l = l / gcd(l, a[i]) * a[i];        // 最小公倍数 lcm（C++17 的 std::gcd），先除后乘防溢出
                if (l > N) { ok = false; break; }  // 超过 N 就不用算了
            }
        if (!ok) continue;
        long long cnt = N / l;                      // 1~N 中是 l 的倍数的个数
        if (__builtin_popcount(S) & 1) ans += cnt;
        else ans -= cnt;
    }
    return ans;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll qpow(ll a, ll b) {
    ll r = 1; a %= MOD;
    while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
    return r;
}
ll inv(ll x) { return qpow(x, MOD - 2); }   // MOD 为素数

/* 法一：卷积递推 O(n²)，适合 n ≤ 5000 且需要完整数列 */
const int MAXN = 5005;
ll cat[MAXN];
void catDP(int n) {
    cat[0] = 1;
    for (int i = 1; i <= n; i++) {
        cat[i] = 0;
        for (int j = 0; j < i; j++)
            cat[i] = (cat[i] + cat[j] * cat[i-1-j]) % MOD;   // 卷积
    }
}

/* 法二：乘式递推 O(n)，适合在线求第 n 项 */
ll cat2(int n) {
    ll c = 1;
    for (int i = 1; i <= n; i++)
        c = c * (4LL * i - 2) % MOD * inv(i + 1) % MOD;   // 2(2i-1)/(i+1)
    return c;
}

/* 法三：通项公式 O(n) 预处理 + O(1) 查询，适合多次询问 */
ll fac[2000006], ifac[2000006];
void initFac(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i-1] = ifac[i] * i % MOD;
}
ll cat3(int n) {
    ll c2n_n = fac[2*n] * ifac[n] % MOD * ifac[n] % MOD;
    return c2n_n * inv(n + 1) % MOD;               // C(2n,n)/(n+1)
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll N; int k;
    cin >> N >> k;
    vector<ll> a(k);
    for (auto& x : a) cin >> x;

    ll ans = 0;
    for (int S = 1; S < (1 << k); S++) {         // 枚举 2^k - 1 个非空子集
        ll l = 1; bool ok = true;
        for (int i = 0; i < k; i++)
            if (S >> i & 1) {
                l = l / gcd(l, a[i]) * a[i];       // lcm（std::gcd），先除后乘防溢出
                if (l > N) { ok = false; break; }
            }
        if (!ok) continue;                      // lcm 超过 N，贡献为 0
        ll cnt = N / l;                           // 1~N 中 l 的倍数个数
        if (__builtin_popcount(S) & 1) ans += cnt;  // 奇数个 → 加
        else                             ans -= cnt;  // 偶数个 → 减
    }
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    vector<ll> f(n + 1, 0);
    f[0] = 1;                        // Cat₀ = 1
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            f[i] += f[j] * f[i - 1 - j];   // 卷积递推 Cat_i = Σ Cat_j · Cat_{i-1-j}
    cout << f[n] << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll C(int n, int k) {          // 组合数（long long，n ≤ 36 不会溢出）
    if (k < 0 || k > n) return 0;
    ll r = 1;
    for (int i = 1; i <= k; i++) r = r * (n - k + i) / i;   // 先乘后除，始终整除
    return r;
}
int main() {
    int n; cin >> n;
    cout << C(2*n, n) - C(2*n, n + 1) << "\n";   // Cat_n = C(2n,n) - C(2n,n+1)
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 20100403;

ll qpow(ll a, ll b) {
    ll r = 1; a %= MOD;
    while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
    return r;
}

const int MAXN = 2000006;
ll fac[MAXN], ifac[MAXN];

ll comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

int main() {
    int n, m; cin >> n >> m;
    int N = n + m;

    // 预处理阶乘与阶乘逆元
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i-1] * i % MOD;
    ifac[N] = qpow(fac[N], MOD - 2);
    for (int i = N; i >= 1; i--) ifac[i-1] = ifac[i] * i % MOD;

    // 格路公式：C(n+m, n) - C(n+m, n+1)
    ll ans = (comb(N, n) - comb(N, n + 1) + MOD) % MOD;
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll N; int k;
    cin >> N >> k;
    vector<ll> p(k);
    for (auto& x : p) cin >> x;

    ll bad = 0;                        // 被至少一个 p_i 整除的个数
    for (int S = 1; S < (1 << k); S++) {
        ll prod = 1;
        bool over = false;
        for (int i = 0; i < k; i++)
            if (S >> i & 1) {
                if (prod > N / p[i]) { over = true; break; }  // 乘法溢出保护
                prod *= p[i];
            }
        if (over) continue;                 // 乘积已超过 N，贡献为 0
        ll cnt = N / prod;                   // 1~N 中 prod 的倍数个数
        if (__builtin_popcount(S) & 1) bad += cnt;
        else bad -= cnt;
    }
    cout << N - bad << "\n";              // 补集：一个都不被整除
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll qpow(ll a, ll b) {
    ll r = 1; a %= MOD;
    while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
    return r;
}

int main() {
    int n; cin >> n;
    if (n <= 1) { cout << 1 << "\n"; return 0; }

    int N = 2 * n;
    vector<ll> fac(N + 1), ifac(N + 1);
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i-1] * i % MOD;
    ifac[N] = qpow(fac[N], MOD - 2);
    for (int i = N; i >= 1; i--) ifac[i-1] = ifac[i] * i % MOD;

    // Cat_n = C(2n, n) / (n+1)
    ll c = fac[N] * ifac[n] % MOD * ifac[n] % MOD;
    ll ans = c * qpow(n + 1, MOD - 2) % MOD;
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    // f[i] = i 边形的三角剖分数，答案 = f[n] = Cat_{n-2}
    vector<ll> f(n + 1, 0);
    f[2] = 1;                                    // 退化情形：两个顶点 / 一条边
    for (int i = 3; i <= n; i++)
        for (int k = 2; k <= i - 1; k++)
            f[i] += f[k] * f[i - k + 1];       // 分成左右两个小多边形
    cout << f[n] << "\n";
    return 0;
}

// 答案 = Cat_{n-2} = C(2n-4, n-2) / (n-1)  (mod 1e9+7)
ll triangulation(int n) {
    int m = n - 2;                  // 转成卡特兰下标
    if (m <= 0) return 1;
    ll c = fac[2*m] * ifac[m] % MOD * ifac[m] % MOD;   // C(2m, m)
    return c * qpow(m + 1, MOD - 2) % MOD;            // 除以 m+1
}
// n=5 → m=3 → Cat₃ = 5 ✔
// n=6 → m=4 → Cat₄ = 14 ✔
// n=7 → m=5 → Cat₅ = 42 ✔

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll qpow(ll a, ll b) {
    ll r = 1; a %= MOD;
    while (b) { if (b & 1) r = r * a % MOD; a = a * a % MOD; b >>= 1; }
    return r;
}
ll inv(ll x) { return qpow(x, MOD - 2); }

/* ========== ① 容斥通用骨架 ========== */
// 求 |A1 ∪ ... ∪ An|（或补集）
// for S in 1..2^n-1:
//     cnt = |∩_{i∈S} A_i|   ← 具体问题具体算（整除题里是 N / lcm）
//     若 popcount(S) 为奇数: ans += cnt
//     否则:                  ans -= cnt
// 补集（恰好 0 个）直接用 全集 - ans

ll inclExcl(ll N, vector<ll>& a) {          // 例子：1~N 中能被某个 a[i] 整除的个数
    int n = a.size(); ll ans = 0;
    for (int S = 1; S < (1 << n); S++) {
        ll l = 1; bool ok = true;
        for (int i = 0; i < n; i++) if (S >> i & 1) {
            l = l / gcd(l, a[i]) * a[i];
            if (l > N) { ok = false; break; }
        }
        if (!ok) continue;
        ll c = N / l;
        if (__builtin_popcount(S) & 1) ans += c; else ans -= c;
    }
    return ans;
}

/* ========== ② 卡特兰数三连 ========== */
const int MAXC = 5005;
ll cat[MAXC];
void catDP(int n) {                        // 卷积 O(n²)，n ≤ 5000
    cat[0] = 1;
    for (int i = 1; i <= n; i++) {
        cat[i] = 0;
        for (int j = 0; j < i; j++)
            cat[i] = (cat[i] + cat[j] * cat[i-1-j]) % MOD;
    }
}
ll catLine(int n) {                        // 乘式递推 O(n)
    ll c = 1;
    for (int i = 1; i <= n; i++)
        c = c * (4LL * i - 2) % MOD * inv(i + 1) % MOD;
    return c;
}
ll fac[2000006], ifac[2000006];
ll catFormula(int n) {                     // 通项 O(1)（需先 initFac）
    ll c = fac[2*n] * ifac[n] % MOD * ifac[n] % MOD;
    return c * inv(n + 1) % MOD;
}

/* ========== ③ 格路推广（n 个 1、m 个 0） ========== */
// 答案 = C(n+m, n) - C(n+m, n+1)，n = m 时退化为 Cat_n