组合数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

作者：

小猫你可以吃芝士汉堡 , 2024-01-29 19:28:27 , 所有人可见 , 阅读 230

6

1

组合数

C(n, k) = n! / (k! * (n-k)!)

其中，n!表示n的阶乘，即n! = n * (n-1) * (n-2) * … * 2 * 1
确保n大于等于k，否则结果将为0。另外，当k为0或k等于n时，结果均为1。

组合数1 O(n^2)

询问次数n比较大，a,b比较小，可以递推预处理出所有的结果；O(a^2);

利用公式C(a,b) = C(a-1,b) + C(a-1,b-1)递推的预处理出所有的组合数可能

证明：选出一个特殊的数x，则组合数可以分为：1.包含x的选法2.不包含x的选法，即公式

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

组合数2 O(nlogn)

n相对比较小，a和b 的值相对比较大

利用C(n, k) = n! / (k! * (n-k)!)，预处理出阶乘的结果，再进行运算；

ps:除法求mod 的运算利用逆元；

int fact[N],infact[N];

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;
}

组合数3 O(p * logN * logp)

询问次数很少，但每组询问的数据范围爆大，模数p：[1,1e5]

卢卡斯定理：C(a,b) ≡ C(a%p, b%p) * C(a/p, b/p)（整除，递推的形式） (mod p)

int p;

int C(LL a,LL b)
{
    if(b > a) return 0;

    int res = 1;
    for(int i = 1,j = a;i <= b;i ++, j --)
    {
        res = res * j % p;
        res = res * qmi(j,p-2) % p;
    }

    return res;
}

int lucas(LL a,LL b)
{
    if(a < p && b < p) return C(a,b);
    return (LL)C(a%p,b%p) * lucas(a/p,b/p) % p;
}

组合数4

利用定义直接计算，结果不取模，需要用高精度运算；

获取a的阶乘 `!a` 的质因子p的次数k：

m = a/p + a/p^2 + .. + a/p^k(当p^k > a时停止)
解释：对于1~a中的某个数t，若是p^k的倍数，那在除p^i(i < k)的每一个i都会加一次，共加k次，不重不漏


##  [卡特函数](https://www.acwing.com/problem/content/891/) 

#### 问题描述
给定 n
 个 0
 和 n
 个 1
，它们将按照某种顺序排成长度为 2n
 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0
 的个数都不少于 1
 的个数的序列有多少个。
int get(int a,int p) //返回a的阶乘中质因子p的总次数
{
    int res = 0;
    while(a)
    {
        res += a / p;
        a /= p;
    }
    return res;
}