组合计数

佚名 4年前 (2020-06-07) 算法 709人围观抢沙发百度已收录

组合计数

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

组合计数

1. 算法分析

1.1 组合数/排列数

C[a][b]:从a里面选b个的方案

递推：C[a][b] = C[a-1][b]+C[a-1][b-1] 可以处理到a,b属于[1, 1e4]
公式：C[a][b] = fact[a] * infact[b] * infact[a - b] （fact[a]表示a的阶乘,infact[a]表示a!的逆元）可以处理到a,b属于[1, 1e8]
lucas定理:C[a][b]=C[a%p][b%p] * C[a/p][b/p] 适用于a和b很大，但是p比较小的情景

组合恒等式：
C[n][0]+C[n][1]+...+C[n][n] = 2 ^ n

排列数
A[a][b] = fact[a!] / fact[(a-b)!]

1.2 错排数

定义: 假设有n个元素，n个位置，每个元素都有自己唯一的正确位置，问，所有元素都处在错误位置有多少可能
公式
设f(n) 表示n个元素的错排种数，则f(n)=(n-1)∗(f(n - 1)+f(n − 2))
f(0) = 1, f(1) = 0, f(2) = 1

1.3 卡特兰数

卡特兰数序列

H0	H1	H2	H3	H4	H5	H6
1	1	2	5	14	42	132

公式
$ H(n) = \frac{C[2n][n]}{n+1} (n>=2, n∈N+)$

H(n)=\begin{cases}
\sum_{i=1}^n H(i-1)H(n-i)， n>=2, n∈N+\\
1, n = 0, 1
\end{cases}

$ H(n) = \frac{H(n-1) * (4n - 2)}{n+1} (n>=2, n∈N+) H(n) = C[2n][n] - C[2n][n-1]$

处理的问题

有2n个人排成一行进入剧场。入场费 5 元。其中只有n个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
一个栈（无穷大）的进栈序列为 1,2,3,...,n 有多少个不同的出栈序列？
n个结点可够造多少个不同的二叉树？
n 个不同的数依次进栈，求不同的出栈结果的种数？
n 个 +1 和 n 个 -1 构成 2n 项 a1,a2,...,a2n ，其部分和满足 a1+a2+...+ak>=0 对与 n 该数列为？

2. 板子

2.1 a、b小(a、b~1e4)，模数大

/*
本题的数据量比较小，a和b均为[1, 2000],询问1e4次
可以先把c[a][b]预处理出来，计算4e6次，然后每次O(1)得到答案
*/
#include<bits/stdc++.h>

using namespace std;

int const N = 2e3 + 10, mod = 1e9 + 7;
int c[N][N];  // 记录答案
int n;

// 预处理
void init()
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            if (j == 0) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

int main()
{
    init();  // 预处理
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}

2.2 a、b大(a、b~1e8)，模数大

/*
本题的a,b数据量为[1, 1e5],可以预处理出阶乘,fact[a]表示a的阶乘,infact[a]表示a!的逆元
那么    fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
每次询问是可以按照公式fact[a] * infact[b] * infact[a - b]来O(1)计算出C[a][b]
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int const N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];
int n;

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

// 预处理
void init()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int main()
{
    init();  // 预处理

    // 计算
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}

2.3 a、b大(a、b~1e18)，模数小

/*
本题的a,b数据量为[1, 1e18],但是p的数据量为[1, 1e5]
那么可以使用lucas来处理,C[a][b] = C[a % p][b % p] * C[a / p][b / p]
每次询问的时候可以先预处理出fact[a],infact[a]等参数，然后用lucas公式来处理，
这样时间复杂度为20*1e5*60
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int const N = 1e5 + 10;
LL fact[N], infact[N];
int n;

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

// 预处理
void init(LL p)
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i] = fact[i - 1] * i % p;
        infact[i] = infact[i - 1] * qmi(i, p - 2, p) % p;
    }
}

// 计算C[a][b]
LL C(LL a, LL b, LL p)
{
    return fact[a] * infact[b] % p * infact[a - b] % p;
}

// lucas来处理，适用于p比较小的情况
LL lucas(LL a, LL b, LL p)
{
    if (a < p && b < p) return C(a, b, p);
    else return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main()
{
    // 计算
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        memset(fact, 0, sizeof fact);
        memset(infact, 0, sizeof infact);
        LL a, b, p;
        scanf("%lld %lld %lld", &a, &b, &p);
        init(p);  // 预处理出fact[a], infact[a]等数据
        printf("%lld\n", lucas(a, b, p));
    }
    return 0;
}

2.4 a、b大(a、b~1e7)，模数没有

/*
本题没有取模，那么C[a][b]按照公式算出来会很大，因此需要高精度
然后要是按照公式C[a][b]=(a!) / (b!(a - b)!)这样子算法会很慢，所以考虑把阶乘质因数分解，然后对于
每个质因子的乘积用高精度去运算，这样的时间复杂度为O(n)
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int const N = 5e3 + 10;
int prime[N], cnt, st[N];

// 筛素数
void init(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; ++j)
        {
            st[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

// C = A * n
vector<int> mul(vector<int> &A, int n)
{
    vector<int> C;  // 存储答案
    int t = 0;
    for (int i = 0; i < A.size() || t; ++i)
    {
        if (i < A.size()) t += A[i] * n;
        C.push_back(t % 10);  // 放入当前位的数字
        t /= 10;
    }
    return C;
}   

// 计算阶乘分解：这个算的就是C[a][b]
vector<int> fac(int a, int b)
{
    int c = a - b;
    
    vector<int> res;
    res.push_back(1);
    for (int i = 0; i < cnt; ++i)
    {
        int p = prime[i];  // 当前这个质因子为p
        int s = 0;  // 计算当前这个质因子的次数
        for (int j = a; j; j /= p) s += j / p;  // a里面p的个数
        for (int j = b; j; j /= p) s -= j / p;  // 减掉b里面p的个数
        for (int j = c; j; j /= p) s -= j / p;  // 减掉a-b里面p的个数
        for (int j = 0; j < s; ++j) res = mul(res, p);
    }
    return res;
}

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

int main()
{
    int a, b;
    cin >> a >> b;
    init(N);  // 预处理得到质因子
    vector<int> res = fac(a, b);   // 计算阶乘
    for (int i = res.size() - 1; i >= 0; --i) cout << res[i];
    return 0;
}

3. 例题

3.1 组合数/排列数/乘法原理/加法原理

acwing1309车的放置

/*
可以把一个网格分割成两个矩形，这样子第一个矩形的长和宽位a和b,第二个矩形的长和宽位(a + c)和d
然后答案即为  累加(1~k)C[b][i]*A[a][i]*C[d][k-i]*A[a+c-i][k-i]
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2010, mod = 100003;

int fact[N], infact[N];

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

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

int A(int a, int b)
{
    if (a < b) return 0;
    return (LL)fact[a] * infact[a - b] % mod;
}

int main()
{
    // 预处理
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ )
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod;
    }

    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;

    // 计算答案
    int res = 0;
    for (int i = 0; i <= k; i ++ )
    {
        res = (res + (LL)C(b, i) * A(a, i) % mod * C(d, k - i) % mod * A(a + c - i, k - i)) % mod;
    }

    cout << res << endl;

    return 0;
}

acwing1308方程的解
对于不定方程 a₁+a₂+⋯+a_k−1+a_k=g(x)，其中 k≥1 且 k∈N∗，x 是正整数，g(x)=x^xmod 1000（即 x^x 除以 1000 的余数），x,k 是给定的数。
k~100, x~int, k≤g(x)

/* 可以看出来g(x)的范围只到1000，因此就像1000个小球去拿隔板分割
可以插入隔板的地方有g(x)-1个，隔板有k-1块
然后组合计数C[g(x) - 1][k-1]计算即可 */

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

int const N = 5e3 + 10;
int prime[N], cnt, st[N];

// 筛素数
void init(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; ++j)
        {
            st[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

// C = A * n
vector<int> mul(vector<int> &A, int n)
{
    vector<int> C;  // 存储答案
    int t = 0;
    for (int i = 0; i < A.size() || t; ++i)
    {
        if (i < A.size()) t += A[i] * n;
        C.push_back(t % 10);  // 放入当前位的数字
        t /= 10;
    }
    return C;
}   

// 计算阶乘分解：这个算的就是C[a][b]
vector<int> fac(int a, int b)
{
    int c = a - b;
    
    vector<int> res;
    res.push_back(1);
    for (int i = 0; i < cnt; ++i)
    {
        int p = prime[i];  // 当前这个质因子为p
        int s = 0;  // 计算当前这个质因子的次数
        for (int j = a; j; j /= p) s += j / p;  // a里面p的个数
        for (int j = b; j; j /= p) s -= j / p;  // 减掉b里面p的个数
        for (int j = c; j; j /= p) s -= j / p;  // 减掉a-b里面p的个数
        for (int j = 0; j < s; ++j) res = mul(res, p);
    }
    return res;
}

int k, x;

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

int main()
{
    int k, x;
    cin >> k >> x;
    int a, b;
    a = qmi(x, x, 1000) - 1, b = k - 1;
    init(N);  // 预处理得到质因子
    vector<int> res;
    res = fac(a, b);   // 计算阶乘
    for (int i = res.size() - 1; i >= 0; --i) cout << res[i];
    return 0;
}

acwing1310数三角形
给定一个 n×m 的网格，请计算三点都在格点上的三角形共有多少个。
n、m~1e3

/*
总的三角形数目=所有网格点选三个点-横的-竖的-斜的
所有网格点选三个点=C((m + 1) * (n + 1), 3)
横的 = (m + 1) * C(n + 1)
竖的 = (n + 1) * C(m + 1)
斜的 = 2ll * (gcd(i, j) - 1) * (n - i + 1) * (m - j + 1)
斜的可以这样理解:最小单位就是gcd(i, j)=1的点对，一旦gcd(i, j)=k,那么就是表明(0, 0)和(i, j)之间有k个点，不包括(0, 0),(i, j)
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int n, m;

LL C(LL n) {
    return n * (n - 1) * (n - 2) / 6;
}

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin >> n >> m;
    LL res = C((m + 1) * (n + 1)) - (m + 1) * C(n + 1) - (n + 1) * C(m + 1);  // 总的-横的-竖的
    
    // 减去斜的
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            res -= 2ll * (gcd(i, j) - 1) * (n - i + 1) * (m - j + 1);
        }
    }
    cout << res;
    return 0;
}

acwing213古代猪文
给定整数n,q，计算q^{∑d|nC[n][d]}mod999911659。
n、q~1e9

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int const N = 1e5 + 10, mod = 999911659;
LL fact[N][10], infact[N][10], factors[N], factors_cnt, prime[N], prime_cnt, a[N], m[N];
int n, q;

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

// 预处理
void init(LL p, int idx)
{
    fact[0][idx] = infact[0][idx] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i][idx] = fact[i - 1][idx] * 1ll * i % p;
        infact[i][idx] = infact[i - 1][idx] * 1ll * qmi(i, p - 2, p) % p;
    }
}

// 计算C[a][b]
LL C(LL a, LL b, LL p, int idx)
{
    return fact[a][idx] * 1ll * infact[b][idx] % p * infact[a - b][idx] % p;
}

// lucas来处理，适用于p比较小的情况
LL lucas(LL a, LL b, LL p, int idx)
{
    if (a < p && b < p) return C(a, b, p, idx);
    else return C(a % p, b % p, p, idx) * lucas(a / p, b / p, p, idx) % p;
}

void get_divisors(int x)
{
    for (int i = 1; i <= x /i; ++i)  // 枚举到sqrtx(x)
    {
        if (x % i == 0)  // 如果能够整除
        {
            factors[factors_cnt++] = i;  // 放入i
            if (i != x / i) factors[factors_cnt++] = x / i;  // x/i不等于i，也放入答案中
        }
    }
    return;
}

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)  // b==0时，x=1， y=0
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x); // b != 0时，gcd(a, b) = gcd(b, a % b), x = x， y = y - a/b * x;
    y -= a / b * x;
    return d;
}

//a, m --- 第i个方程表示x ≡ ai(mod mi)
// n---- 方程个数
LL CRT( LL a[], LL m[], LL n )//x ≡ ai(mod mi)
{
    LL M = 1;
    for(int i = 0;i<n;++i) M *= m[i];
    LL ret = 0;
    for(int i=0;i<n;++i)
    {
        LL x,y;
        LL tm = M/m[i];
        exgcd(tm,m[i],x,y);//调用外部函数：拓展欧几里得
        ret = (ret+tm*x*a[i])%M;
    }
    return (ret+M)%M;
}


int main() {
    cin >> n >> q;
    if (q == mod) {
        cout << 0 << endl;
        return 0;
    }
    get_divisors(n);  // 得到n的约数
    
    // 把999911659分解质因数结果
    prime_cnt = 4;
    prime[0] = 2, prime[1] = 3, prime[2] = 4679, prime[3] = 35617;
    
    // 得到CRT的模数
    for (int i = 0; i < prime_cnt; ++i) {
        m[i] = prime[i];
        init(prime[i], i);
    }
    
    // 得到CRT的ai
    for (int i = 0; i < prime_cnt; ++i) {
        LL t = 0;
        for (int j = 0; j < factors_cnt; ++j) {
            t = (t + lucas(n, factors[j], prime[i], i)) % prime[i] ;
        }
        a[i] = t;
    }
    
    // CRT得到: 累加[C[n][d], d|n]
    LL t = CRT(a, m, prime_cnt);
    cout << qmi(q, t, mod);
    return 0;
}

3.2 错排数

acwing230排列计数
求有多少种长度为 n 的序列 A，满足以下条件：
1、1 ~ n 这 n 个数在序列中各出现了一次。
2、若第 i 个数 A[i] 的值为 i，则称 i 是稳定的，序列恰好有 m 个数是稳定的。
由于满足条件的序列可能很多，所以请你将序列数对 1e9+7 取模后输出。

// 答案为:C[n][m]*f[n-m], f[i]为个数为i时的错排数
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int const N = 1e6 + 10, mod = 1e9 + 7;
int fact[N], infact[N], f[N];
int n, m, t;

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

// 预处理
void init()
{
    fact[0] = infact[0] = 1;
    f[0] = 1, f[1] = 0, f[2] = 1;
    for (int i = 1; i < N; ++i)
    {
        if (i >= 3) f[i] = (i - 1) * ((f[i - 1] + 0ll + f[i - 2]) % mod) % mod;
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int C(int a, int b) {
    return fact[a] * 1ll * infact[b] % mod * infact[a - b] % mod;
}

int main()
{
    init();  // 预处理

    cin >> t;
    while (t--) {
        scanf("%d%d", &n, &m);
        printf("%d\n", (C(n, m) * 1ll * f[n - m]) % mod);
    }
    return 0;
}

3.3 卡特兰数

acwing889满足条件的01序列
给定n个0和n个1，它们将按照某种顺序排成长度为2n的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。输出的答案对109+7取模。
n~1e5

// 任何一条经过y=x+1的上的点的线都可以投影到(n-1,n+1)，因此方案数为c[2n][n]-c[2n][n-1]=c[2n][n]/(n+1)
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int const N = 2e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];
int n;

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

// 预处理
void init()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int C(int a, int b) {
    return fact[a] * (LL)infact[b] % mod * infact[a - b] % mod;
}

int main()
{
    init();  // 预处理

    // 计算
    cin >> n;
    int res = (LL)fact[2 * n] * infact[n] % mod * infact[n] % mod * qmi(n + 1, mod - 2, mod) % mod;  // c[2n][n]-c[2n][n-1] = c[2n][n] / (n + 1)
    cout << res << endl;
    return 0;
}

acwing1315网格
某城市的街道呈网格状，左下角坐标为 A(0,0)，右上角坐标为 B(n,m)，其中 n≥m。现在从 A(0,0) 点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点 (x,y) 都要满足 x≥y，请问在这些前提下，到达 B(n,m) 有多少种走法。
n,m~5000

// 按照卡特兰数的推导方法，最后答案为:C(n + m, n) - C(n + m, m -1)
// 然后组合计数处理即可
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int const N = 5e4 + 10;
int prime[N], cnt, st[N];

// 筛素数
void init(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; ++j)
        {
            st[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

// C = A - B
vector <int> sub(vector<int> &A, vector<int> &B)
{
    vector <int> C;  // 用来存储答案
    int t = 0;  // 记录是否去高位借位
    for (int i = 0; i < A.size(); ++i)
    {
        t = A[i] - t;
        if (i < B.size() ) t -= B[i];  
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1; // 复原t
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();  // 去除高位的前导0
    return C;
}

// C = A * n
vector<int> mul(vector<int> &A, int n)
{
    vector<int> C;  // 存储答案
    int t = 0;
    for (int i = 0; i < A.size() || t; ++i)
    {
        if (i < A.size()) t += A[i] * n;
        C.push_back(t % 10);  // 放入当前位的数字
        t /= 10;
    }
    return C;
}   

// 计算阶乘分解：这个算的就是C[a][b]
vector<int> fac(int a, int b)
{
    int c = a - b;
    
    vector<int> res;
    res.push_back(1);
    for (int i = 0; i < cnt; ++i)
    {
        int p = prime[i];  // 当前这个质因子为p
        int s = 0;  // 计算当前这个质因子的次数
        for (int j = a; j; j /= p) s += j / p;  // a里面p的个数
        for (int j = b; j; j /= p) s -= j / p;  // 减掉b里面p的个数
        for (int j = c; j; j /= p) s -= j / p;  // 减掉a-b里面p的个数
        for (int j = 0; j < s; ++j) res = mul(res, p);
    }
    return res;
}

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

int main()
{
    int n, m;
    cin >> n >> m;
    init(N);  // 预处理得到质因子
    vector<int> A = fac(n + m, n), B = fac(n + m, m - 1);  // 计算C(n+m, n)和C(n + m, m - 1)
    vector<int> res = sub(A, B);   // 计算阶乘
    for (int i = res.size() - 1; i >= 0; --i) cout << res[i];
    return 0;
}

acwing1316有趣的数列
我们称一个长度为 2n 的数列是有趣的，当且仅当该数列满足以下三个条件：

它是从 1 到 2n 共 2n 个整数的一个排列 {ai}；
所有的奇数项满足 a1<a3<⋯<a2n−1 ，所有的偶数项满足 a2<a4<⋯<a2n；
任意相邻的两项 a2i−1 与 a2i (1≤i≤n) 满足奇数项小于偶数项，即：a2i−1<a2i。

任务是：对于给定的 n，请求出有多少个不同的长度为 2n 的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 modP 的值。
n_1e6,P1e9

/*
分析本题，可以发现必须满足，前n项中，奇数项个数大于偶数项个数，那么满足卡特兰数性质
那么就是要要求C[2n][n]-C[2n][n-1] ,然后本题mod的数p可能和a不互质，因此a可能不存在逆元，可以考虑阶乘分解的算法
mod p只要在每次求完质因数的次数后调用快速幂，然后模掉即可
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n, p;
int primes[N], cnt;
bool st[N];

// 线性筛法
void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if  (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

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

// 算每个质因子的次数
int get(int n, int p)
{
    int s = 0;
    while (n)
    {
        s += n / p;
        n /= p;
    }
    return s;
}

// 求C[a][b]
int C(int a, int b)
{
    int res = 1;
    for (int i = 0; i < cnt; i ++ )
    {
        int prime = primes[i];
        int s = get(a, prime) - get(b, prime) - get(a - b, prime);  // 算每个质因子的次数

        res = (LL)res * qmi(prime, s) % p;
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &p);
    init(n * 2);

    cout << (C(n * 2, n) - C(n * 2, n - 1) + p) % p << endl;

    return 0;
}

扫码关注我们

微信号：SRE实战

拒绝背锅运筹帷幄

赞 0 赏分享

转载请注明 : 文章转载自小翔博客组合计数

本文标题：组合计数

本文链接：https://liuyixiang.com/post/114308.html

上一篇 : 概率与期望

下一篇 : 矩阵乘法

评论列表暂无评论

发表评论

组合计数

组合计数

1. 算法分析

1.1 组合数/排列数

1.2 错排数

1.3 卡特兰数

2. 板子

2.1 a、b小(a、b~1e4)，模数大

2.2 a、b大(a、b~1e8)，模数大

2.3 a、b大(a、b~1e18)，模数小

2.4 a、b大(a、b~1e7)，模数没有

3. 例题

3.1 组合数/排列数/乘法原理/加法原理

3.2 错排数

3.3 卡特兰数

选择打赏方式：

选择分享方式：

Petter

101481

12

121484300

« 2024年2月 »
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29

组合计数

组合计数

1. 算法分析

1.1 组合数/排列数

1.2 错排数

1.3 卡特兰数

2. 板子

2.1 a、b小(a、b~1e4)，模数大

2.2 a、b大(a、b~1e8)，模数大

2.3 a、b大(a、b~1e18)，模数小

2.4 a、b大(a、b~1e7)，模数没有

3. 例题

3.1 组合数/排列数/乘法原理/加法原理

3.2 错排数

3.3 卡特兰数

选择打赏方式：

选择分享方式：

Petter

101481

12

121484300

User Login

帐号或密码错误,请重试.