排列组合

组合数

模版

递推(模数任意)阶乘(模数质数)筛法(模数任意)大组合数(模数质数)

利用 \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\) 递推求解。

预处理 \(O(n^2)\)，查询 \(O(1)\)。

代码

C++
using i64 = long long;
const i64 P = 1000000007;
namespace Combination {
    i64 c[5001][5001];
    void init() {
        c[0][0] = 1;
        for (int i = 1 ; i <= 5000 ; i++) {
            c[i][0] = 1;
            for (int j = 0 ; j <= i ; j++) {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
            }
        }
    }
    i64 get(int n, int r) {
        return c[n][r];
    }
} // Combination

预处理阶乘和逆元求解。

预处理 \(O(n)\)，查询 \(O(1)\)。

代码

C++
using i64 = long long;
template<const i64 mod = 1000000007>
struct Combination {
    int n;
    vector<i64> _fac, _invfac, _inv;
    Combination() : n(0), _fac{1}, _invfac{1}, _inv{0} {}
    Combination(int n) : Combination() {}
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1 ; i <= m ; i++) {
            _fac[i] = _fac[i - 1] * i % mod;
        }
        _invfac[m] = qpow(_fac[m]);
        for (int i = m ; i > n ; i--) {
            _invfac[i - 1] = _invfac[i] * i % mod;
            _inv[i] = _invfac[i] * _fac[i - 1] % mod;
        }
        n = m;
    }
    i64 fac(int m) {
        if (m > n) init(m << 1);
        return _fac[m];
    }
    i64 invfac(int m) {
        if (m > n) init(m << 1);
        return _invfac[m];
    }
    i64 inv(int m) {
        if (m > n) init(m << 1);
        return _inv[m];
    }
    i64 C(int n, int m) {
        if (n < m || m < 0) return 0LL;
        return fac(n) * invfac(m) % mod * invfac(n - m) % mod;
    }
    i64 operator()(int n, int m) {
        return C(n, m);
    }
    static i64 qpow(i64 a, i64 b = mod - 2, i64 res = 1) {
        while (b) {
            if (b & 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
};
Combination<998244353> C;

筛出 \(n\) 以内的质因数，枚举质因子求解。

预处理 \(O(n)\)，查询 \(O(prime(n)*\log p)\)。

代码

C++
            using i64 = long long;
namespace EulerSieve {
    vector<int> prime;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    break;
                }
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using EulerSieve::prime;
int __EulerInit = []() {
    EulerSieve::primeInit(2000005);
    return 0;
}();
namespace Combination {
    i64 qpow(i64 a, i64 b, i64 P, i64 res = 1) {
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }
    i64 C(int n, int m, int P) {
        if (n < m || m < 0) return 0LL;
        i64 res = 1;
        for (auto &i : prime) {
            if (i > n * 2) {
                break;
            }
            int s = 0;
            int k = n;
            while (k > 0) {
                k /= i;
                s += k;
            }
            k = n - m;
            while (k > 0) {
                k /= i;
                s -= k;
            }
            k = m;
            while (k > 0) {
                k /= i;
                s -= k;
            }
            res = res * qpow(i, s, P) % P;
        }
        return res;
    }
} // Combination
using Combination::C;

卢卡斯定理 \(C_n^m\equiv C_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}*C_{n\mod p}^{m\mod p}\pmod p\)

无预处理，查询 \(O(p*\log_p(n))\)

预处理 \(O(p)\)，查询 \(O(p+\log_p(n))\)

代码

无预处理预处理

C++
using i64 = long long;
namespace Lucas {
    i64 P = 1000000007;
    i64 qpow(i64 a, i64 b = P - 2, i64 res = 1) {
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }
    i64 C(i64 n, i64 m) {
        i64 x = 1, y = 1;
        if (n < m) return 0;
        else if (n == m) return 1;
        for (int i = n - m + 1 ; i <= n ; i++) x = x * i % P;
        for (int i = 1 ; i <= m ; i++) y = y * i % P;
        return x * qpow(y) % P;
    }
    i64 get(i64 n, i64 m) {
        if (m == 0) return 1;
        return (C(n % P, m % P) * get(n / P, m / P)) % P;
    }
    i64 get(i64 n, i64 m, i64 P) {
        Lucas::P = P;
        return get(n, m);
    }
} // Lucas

C++
namespace Lucas {
    const long long mod = 10007;
    int fact[mod], invf[mod];
    static long long qinv(long long a) {
        long long res = 1, b = mod - 2;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    auto _Lucas_Init = []() {
        fact[0] = 1;
        for (int i = 1 ; i < mod ; i++) {
            fact[i] = 1LL * fact[i - 1] * i % mod;
        }
        invf[mod - 1] = qinv(fact[mod - 1]);
        for (int i = mod - 1 ; i > 0 ; i--) {
            invf[i - 1] = 1LL * invf[i] * i % mod;
        }
        return 0;
    }();
    long long C(long long n, long long m) {
        if (n < m) return 0;
        else if (n == m) return 1;
        return fact[n] * invf[m] % mod * invf[n - m] % mod;
    }
    long long get(long long n, long long m) {
        if (m == 0) return 1;
        return (C(n % mod, m % mod) * get(n / mod, m / mod)) % mod;
    }
} // Lucas

模版

P3807 【模板】卢卡斯定理/Lucas 定理 - 洛谷

重复排列

从n个不同的物体中，允许重复地选取r个物体的排列有 \(n^r\) 种方案

重复组合

从n个不同的物体中，允许重复地选取r个物体的组合有 \(C_{n+r-1}^r\)

不全相异全排列

第 \(i\) 种物品有 \(n_i\) 个，全排列数为 \(\dfrac{n!}{n_1!\cdot{n_2!}\cdot\cdots\cdot{n_k!}}\)

圆周排列

从N个元素中取出R个元素形成的圆周排列方案数为 \(\dfrac{A_N^R}{R}\)

插板法

正整数和的数目

\(x_1+x_2+…+x_k=n\) 的正整数解的组数 \(C_{n-1}^{k-1}\)

非负整数和的数目

\(x_1+x_2+…+x_k=n\) 的非负整数解的组数 \(C_{n+k-1}^{k-1}\)

不同下界整数和的数目

\(x_1+x_2+…+x_k=n\) 的解的组数，其中 \(x\geq{}a_i\)

\(C_{n-\sum{}a_i+k-1}^{n-\sum{}a_i}\)

不相邻的排列

n 排列中选 k 个数，这 k 个数中任何两个数都不相邻的组合有 \(C_{n-k+1}^k\)

十二重计数法

十二重计数法	球(n)	盒子(m)	限制条件	方案数
1	不同	不同	无	\(m^n\)
2	不同	不同	至多装一个球	\(A_m^n\)
3	不同	不同	至少装一个球	\(\sum_{i=0}^m(-1)^i{(m-i)}^nC_m^i\) 或者第二类斯特林数 \(m!*S_2(n,m)\)
4	不同	相同	无	第二类斯特林数 \(\sum_{i=1}^mS_2(n,i)\)
5	不同	相同	至多装一个球	\([n\leq{}m]\)
6	不同	相同	至少装一个球	第二类斯特林数 \(S_2(n,m)\)
7	相同	不同	无	\(C_{n+m-1}^{m-1}\)
8	相同	不同	至多装一个球	\(C_m^n\)
9	相同	不同	至少装一个球	\(C_{n-1}^{m-1}\)
10	相同	相同	无	分拆数 \(F(n)\)
11	相同	相同	至多装一个球	\([n\leq{}m]\)
12	相同	相同	至少装一个球	分拆数 \(F(n-m)\)

P5824 十二重计数法 - 洛谷

代码

C++
Combination<998244353> C;
i64 n, m;
i64 solve01() {
    return qpow(m, n);
}
i64 solve02() {
    i64 res = 1;
    for (int i = m - n + 1 ; i <= m ; i++) {
        res = res * i % P;
    }
    return res;
}
Poly<Int> S2;
i64 solve03() {
    i64 res = C.fac(m);
    res = res * S2[m] % P;
    return res;
}
i64 solve04() {
    i64 res = 0;
    for (int i = 1 ; i <= m ; i++) {
        res = (res + S2[i]) % P;
    }
    return res;
}
i64 solve05() {
    return n <= m;
}
i64 solve06() {
    return S2[m];
}
i64 solve07() {
    return C(n + m - 1, m - 1);
}
i64 solve08() {
    return C(m, n);
}
i64 solve09() {
    return C(n - 1, m - 1);
}
Poly<Int> F;
i64 solve10() {
    return F[n];
}
i64 solve11() {
    return n <= m;
}
i64 solve12() {
    if (n < m) return 0LL;
    return F[n - m];
}
int main() {
    cin >> n >> m;
    S2 = other::Stirling2Row(n);
    S2.resize(max(n, m) + 1);
    F = other::Partition(n, min(n, m));
    cout << solve01() << "\n";
    cout << solve02() << "\n";
    cout << solve03() << "\n";
    cout << solve04() << "\n";
    cout << solve05() << "\n";
    cout << solve06() << "\n";
    cout << solve07() << "\n";
    cout << solve08() << "\n";
    cout << solve09() << "\n";
    cout << solve10() << "\n";
    cout << solve11() << "\n";
    cout << solve12() << "\n";
    return 0;
}

二项式定理

\[ (a+b)^n=\sum_{i=0}^nC_n^i*a^{n-i}*b^i \nonumber \]

二项式反演

记 \(f_k\) 为恰好使用 \(k\) 个不同元素形成特定结构的方案数，\(g_k\) 为使用至多 \(k\) 个不同元素形成特定结构的方案数。

\[ \begin{align} \nonumber g_k&=\sum_{i=0}^kC_n^i*f_i\\ \nonumber f_k&=\sum_{i=0}^kC_n^i*(-1)^{n-i}*g_i \end{align} \]

记 \(f_k\) 为恰好使用 \(k\) 个不同元素形成特定结构的方案数，\(g_k\) 为钦定使用 \(k\) 个不同元素形成特定结构的方案数(有重复方案)。

\[ \begin{align} \nonumber g_k&=\sum_{i=k}^nC_i^k*f_i\\ \nonumber f_k&=\sum_{i=k}^nC_i^k*(-1)^{i-k}*g_i \end{align} \]

组合数性质 | 二项式推论

\[ C_{n+1}^k=C_n^k+C_n^{k-1} \]

\[ C_n^k=\dfrac{n}{k}*C_{n-1}^{k-1} \]

\[ C_{n-1}^k-C_{n-1}^{k-1}=\dfrac{n-2k}{n}*C_n^k \]

\[ C_n^i*C_i^m=C_n^m*C_{n-m}^{i-m} \]

\[ \sum_{i=0}^nC_n^i=2^n \]

\[ \sum_{i=0}^kC_{n+i-1}^i=C_{n+k}^k \]

\[ \sum_{i=0}^{n-k}\dfrac{(-1)^i*(n+1)}{k+i+1}*C_{n-k}^i=\dfrac{1}{C_n^k} \]

\[ \sum_{i=L}^RC_{n+i}^i=C_{n+R+1}^R-C_{n+L}^{L-1} \]

\[ \sum_{i=L}^RC_i^n=C_{R+1}^{n+1}-C_L^{n+1} \]

\[ \sum_{i=0}^n(C_n^i)^2=C_{2n}^n \]

\[ \sum_{i=0}^nC_{a+n-1-i}^{a-1}*C_{b+i-1}^{b-1}=C_{a+b+n-1}^{a+b-1} \]

\[ \sum_{i=0}^kC_n^i*C_m^{k-i}=C_{n+m}^k \]

\[ \sum_{i=-r}^{s}C_n^{r+i}*C_m^{s-i}=C_{n+m}^{r+s} \]

\[ \sum_{i=0}^mC_n^i*C_m^i=C_{n+m}^m \]

\[ \sum_{i=1}^nC_n^i*C_n^{i-1}=C_{2n}^{n-1} \]

\[ (C_{n+k}^k)^2=\sum_{i=0}^k(C_k^i)^2*C_{n+2k-i}^{2k} \]

\[ \sum_{i=0}^n(-1)^i*C_n^i=[n=0] \]

\[ \sum_{i=0}^ni*C_n^i=n*2^{n-1} \]

\[ \sum_{i=0}^ni^2*C_n^i=n*(n+1)*2^{n-2} \]

\[ \sum_{i=0}^nC_i^k=C_{n+1}^{k+1} \]

\[ \sum_{i=0}^nC_{n-i}^i=F_{n+1}(\text{斐波那契数列}) \]