[数论](7)组合数

组合数

C a b 表示从a个苹果中选择b个苹果

情况一:

image-20210518232037917

思路(来源acwing中Struggle佬):

image-20210518232514332

伪码:

//C[a][b] 表示从 a 种数字中选取 b 个数字的方案数
//情况1: 不选 则 C[a][b] = C[a-1][b]; 需要从 a - 1 中 挑选 b 个数
//情况2: 选 则 C[a][b] = C[a-1][b-1]; 需要从 a - 1 中 挑选b-1个数
从a中选取b个数的方案数(1<=a<=b<=2000):
    定义一个状态数组dp,存储方案的变化
    通过公式可得出状态初始条件:
        若 [b=0] 则代表从 a 个数中挑选 0 个数 方案数只能是1(什么都不选)
        则 if(b==0) f[a][b]=1
    通过公式可得出状态转移方程:
        f[a][b]=f[a-1][b-1]+f[a-1][b]

源码:

#define N 2020
int n,C[N][N];
const int mod=1e9+7;
void Init(){//打表
    for(int a=0;a<N;a++)
        for(int b=0;b<=a;b++)
            if(!b) C[a][b]=1;
            else C[a][b]=(C[a-1][b]+C[a-1][b-1])%mod;
    return ;
}

情况二:

image-20210518233429441

思路(来源acwing的acw_weian佬):

image-20210519020427351

伪码:

因为其要对1e9+7取模,而1e9+7是质数,则可用快速幂求得逆元套用上述公式求解:
    定义fact[i]   表示 i 得乘阶
    定义infact[i] 表示 i 逆元得乘阶
    即可将公式Cab转换为 fact[a]*infact[a-b]*infact[b]
        预处理出来[1-100010]的乘阶和其逆元乘阶
        然后套用公式求解即可

源码:

typedef long long LL;//数据可能会爆int,保险起见用long long
(io十年一场空,不开long long 见祖宗 /(ㄒoㄒ)/~~)
#define N 100010
LL fact[N], infact[N];//乘阶表和逆元乘阶表
const int p = 1e9 + 7;
LL qmi(LL a, LL k) {//快速幂模板
    LL res = 1 % p;
    while (k) {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}
void Init() {
    fact[0] = infact[0] = 1;//当b为0时,方案数为1
    for (int i = 1; i < N; i++) {
        fact[i] = i * fact[i - 1] % p;
        infact[i] = infact[i - 1] * qmi(i, p - 2) % p;//费马小定理求出逆元
    }
    return;
}

情况三:

image-20210518235900588

当数据很大时,不能将其阶乘预处理,则使用lucas定理

思路(来自acwing的嘤嘤嘤佬):

image-20210519020442010

伪码:

预先写好快速幂的模板
求C(a,b)的函数:
    定义res(long long) 为1
    根据公式:
        C(a,b)=a*(a-1)*(a-2)....*(a-b+1) / 1*2*3....*b (除法无法确定精度,这里用快速幂求逆元进行相乘)求得C(a,b)得值
    
    lucas定理:采用递归得方式根据公式求得答案
        若a和b均比p小,则直接调用C(a,b)函数即可
        否则需要根据公式返回C(a%p,b%p)*lucas(a/p,b/p)
            这儿后边继续递归lucas函数是因为
            a%p,b%p后已经在p得范围内
            而a/p,b/p则不一定会比p小,所以需要递归继续判断
            
(源码较长,伪码只助于理解,具体请看视频教学根据源码推导)

源码:

#include<iostream>
#include<cstring>
using namespace std;
int n;
typedef long long LL;
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;
}
LL C(LL a,LL b,LL p){
    LL res=1;
    for(LL i=1,j=a;i<=b;i++,j--)
        res=(res*j%p)*(qmi(i,p-2,p)%p);//根据公式采用逆元求解
    return res%p;//返回前需先将答案 mod p 内
}
LL lucass(LL a,LL b,LL p){
    if(a<p&&b<p) return C(a,b,p);
    return C(a%p,b%p,p)*lucass(a/p,b/p,p)%p;
    //需要递归得原因:a/p b/p 也许比p大,需要将其 mod 到 p 内 
}
int main(){
    scanf("%d",&n);
    while(n--){
        //给定n对a,b,p 求C(a,b) mod p
        LL a,b,p;
        scanf("%lld %lld %lld",&a,&b,&p);
        LL t = lucass(a,b,p);
        printf("%lld\n",t);
    }
    return 0;
}

情况四:

image-20210519020453710

思路:

image-20210519020504306

用一句话来概括就是:对极值分解质因数,然后减去(a-b)和b中这个质因数得个数

伪码:

我们将问题转化为公式后,这个除法又不好搞定
当分子和分母中是由同一个因数构成得,他们即可约去
而b一定比a小,我们可以将思路转化为:
    [构成分子的所有质因子] - [构成分母的所有质因子]
剩下的质因子既是他们答案的积
如何证明这个思路:
    用小的测试数据代入思路手算一遍即可,了解了解,反正磨磨唧唧弄懂原理,比赛还不是使劲想模板

源码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
int prime[N], cnt, sum[N], ans[N],ansSize = N - 1;
bool st[N];
void get_prime(int x) {//线性筛模板
    for (int i = 2; i <= x; i++) {
        if (!st[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] <= x / i; j++) {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
    return;
}
int get(int n, int p) {//求n中p的个数,对应题目就是求a中当前p这个质因子的个数
    int res = 0;
    while (n) {
        res += n / p;
        n /= p;
    }
    return res;
}
void mul(int x) {//高精度乘法
    int t = 0, i;
    for (i = N - 1; i >= ansSize; i--) {
        int u = ans[i] * x + t;
        ans[i] = u % 10;
        t = u / 10;
    }
    while (t) {
        ans[i--] = t % 10;
        t /= 10;
    }
    ansSize = i + 1;
    return;
}
int main() {
    int a, b;
    cin >> a >> b;
    //1.筛质数
    get_prime(a);

    //通过公式求得C(a,b)中有多少个质因子
    for (int i = 0; i < cnt; i++)
        sum[i] = get(a, prime[i]) - get((a - b), prime[i]) - get(b, prime[i]);

    //通过高精度乘法将所有质因子相乘
    ans[ansSize] = 1;
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < sum[i]; j++)
            mul(prime[i]);
    //  printf("%d %d",prime[])
    }
    for (int i = ansSize; i < N; i++) printf("%d", ans[i]);
    return 0;
}

本文链接:

https://nullcode.fun/145.html
1 + 6 =
快来做第一个评论的人吧~