//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "组合数学": {
        "prefix": "acm-7.2Comb",
        "body": [
            "class Combinatorics {",
            "private:",
            "    vector<ll> fact, inv_fact;",
            "    int max_n;",
            "    ",
            "public:",
            "    // 预处理阶乘和逆阶乘，O(n)",
            "    Combinatorics(int n) : max_n(n) {",
            "        fact.resize(n + 1);",
            "        inv_fact.resize(n + 1);",
            "        ",
            "        fact[0] = 1;",
            "        for (int i = 1; i <= n; i++) {",
            "            fact[i] = fact[i - 1] * i % MOD;",
            "        }",
            "        ",
            "        inv_fact[n] = inv(fact[n]);",
            "        for (int i = n - 1; i >= 0; i--) {",
            "            inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;",
            "        }",
            "    }",
            "    ",
            "    // 快速幂计算逆元，O(log MOD)",
            "    ll inv(ll x) {",
            "        return qpow(x, MOD - 2);",
            "    }",
            "    ",
            "    // 快速幂，O(log exponent)",
            "    ll qpow(ll a, ll b) {",
            "        ll res = 1;",
            "        while (b) {",
            "            if (b & 1) res = res * a % MOD;",
            "            a = a * a % MOD;",
            "            b >>= 1;",
            "        }",
            "        return res;",
            "    }",
            "    ",
            "    // 组合数C(n,k)，O(1)",
            "    ll C(int n, int k) {",
            "        if (k < 0 || k > n) return 0;",
            "        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;",
            "    }",
            "    ",
            "    // 排列数A(n,k)，O(1)",
            "    ll A(int n, int k) {",
            "        if (k < 0 || k > n) return 0;",
            "        return fact[n] * inv_fact[n - k] % MOD;",
            "    }",
            "    ",
            "    // 卢卡斯定理计算组合数，适用于n,k很大但MOD较小的情况",
            "    ll Lucas(ll n, ll k) {",
            "        if (k == 0) return 1;",
            "        return C(n % MOD, k % MOD) * Lucas(n / MOD, k / MOD) % MOD;",
            "    }",
            "    ",
            "    // 第二类斯特林数S(n,k)，将n个元素划分为k个非空子集，O(nk)",
            "    ll Stirling2(int n, int k) {",
            "        ll res = 0;",
            "        for (int i = 0; i <= k; i++) {",
            "            ll term = C(k, i) * qpow(i, n) % MOD;",
            "            if ((k - i) % 2) {",
            "                res = (res - term + MOD) % MOD;",
            "            } else {",
            "                res = (res + term) % MOD;",
            "            }",
            "        }",
            "        return res * inv_fact[k] % MOD;",
            "    }",
            "    ",
            "    // 贝尔数B(n)，基于第二类斯特林数的实现，O(n^2)",
            "    // B(n) = Σ S(n,k) for k=0 to n",
            "    ll Bell_Stirling(int n) {",
            "        ll res = 0;",
            "        for (int k = 0; k <= n; k++) {",
            "            res = (res + Stirling2(n, k)) % MOD;",
            "        }",
            "        return res;",
            "    }",
            "    ",
            "    // 贝尔数B(n)，基于动态规划的实现，O(n^2)",
            "    // 使用递推关系：B(n+1) = Σ C(n,k)*B(k) for k=0 to n",
            "    ll Bell_DP(int n) {",
            "        if (n == 0) return 1;",
            "        vector<ll> bell(n + 1);",
            "        bell[0] = 1;",
            "        ",
            "        for (int i = 1; i <= n; i++) {",
            "            bell[i] = 0;",
            "            for (int k = 0; k < i; k++) {",
            "                bell[i] = (bell[i] + C(i - 1, k) * bell[k]) % MOD;",
            "            }",
            "        }",
            "        return bell[n];",
            "    }",
            "    ",
            "    // 卡特兰数，O(1)",
            "    ll Catalan(int n) {",
            "        return C(2 * n, n) * inv(n + 1) % MOD;",
            "    }",
            "    ",
            "    // 错位排列数，O(n)预处理后O(1)查询",
            "    ll Derangement(int n) {",
            "        if (n == 0) return 1;",
            "        if (n == 1) return 0;",
            "        // D(n) = (n-1)*(D(n-1)+D(n-2))",
            "        vector<ll> d(n + 1);",
            "        d[0] = 1;",
            "        d[1] = 0;",
            "        for (int i = 2; i <= n; i++) {",
            "            d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD;",
            "        }",
            "        return d[n];",
            "    }",
            "    ",
            "    // 计算gcd，O(log min(a,b))",
            "    ll gcd(ll a, ll b) {",
            "        return b == 0 ? a : gcd(b, a % b);",
            "    }",
            "    ",
            "    // 计算lcm，O(log min(a,b))",
            "    ll lcm(ll a, ll b) {",
            "        return a / gcd(a, b) * b;",
            "    }",
            "    ",
            "    // 扩展欧几里得算法，求解ax + by = gcd(a,b)",
            "    ll ext_gcd(ll a, ll b, ll &x, ll &y) {",
            "        if (b == 0) {",
            "            x = 1;",
            "            y = 0;",
            "            return a;",
            "        }",
            "        ll d = ext_gcd(b, a % b, y, x);",
            "        y -= a / b * x;",
            "        return d;",
            "    }",
            "    ",
            "    // 中国剩余定理，求解x ≡ a_i (mod m_i)",
            "    ll CRT(const vector<ll> &a, const vector<ll> &m) {",
            "        ll M = 1, x = 0;",
            "        int n = a.size();",
            "        for (int i = 0; i < n; i++) M *= m[i];",
            "        ",
            "        for (int i = 0; i < n; i++) {",
            "            ll Mi = M / m[i];",
            "            ll y, z;",
            "            ext_gcd(Mi, m[i], y, z);",
            "            x = (x + a[i] * Mi % M * y % M) % M;",
            "        }",
            "        return (x + M) % M;",
            "    }",
            "    ",
            "    // 欧拉函数，计算小于n且与n互质的数的个数，O(sqrt(n))",
            "    ll EulerPhi(ll n) {",
            "        ll res = n;",
            "        for (ll i = 2; i * i <= n; i++) {",
            "            if (n % i == 0) {",
            "                res = res / i * (i - 1);",
            "                while (n % i == 0) n /= i;",
            "            }",
            "        }",
            "        if (n > 1) res = res / n * (n - 1);",
            "        return res;",
            "    }",
            "};",
            "",
            "Combinatorics comb(1000000); // 预处理1e6以内的阶乘"
        ],
        "description": "插入 组合数学"
    }
}