信竞-排列组合

HYLW · 2023-12-19 15:39:16 · 算法·理论

排列组合

一、求组合数

对于相同的问题：

给定 n 组询问，每组询问给定两个整数 a ，b ，请你输出C_a^b\mod(10^9+7) 的值。

现进行难度递增的解决方案.

Frist time

1\leq n\leq 10000,1\leq b \leq a \leq 2000

分析一下：假如暴力做，即利用 C_a^b=\frac{(a-b+1)\cdot (a-b+2) ……(a-1)\cdot (a-2)\cdot a}{1\cdot2\cdot3 ……b} 计算，则每次最多 2000 次运算，最多 10000 次询问，则 O()=2\times10^7 ，还是相当慢的。

然而我们知道，这道题的核心是组合数，而组合数有着如下性质：

C_n^m=C_{n-1}^m+C_{n-1}^{m-1}(n>1)

由此可以想到把所有 C_a^b 预处理出来，发现，此时 O()=4\times10^6,显然是一种比较快的方式。

我们用一个c[N][N]的二维数组来表示组合数，即得c[i][j]=c[i-1][j-1]+c[i-1][j]，而我们的推导过程如下：

C_n^0=1=C_0^0(m>n,$ 设 $C_n^m=0)

C_1^0=1,C_1^1=\frac{1!}{1!\cdot 0!}=1

C_2^0=1,C_2^1=C_1^1+C_1^0=2,C_2^2=C_1^2+C_1^1=1

C_3^0=1,C_3^1=C_2^0+C_2^1=3,C_3^2=C_2^2+C_2^1=3,C_3^3=C_2^3+C_2^2=1

……

其实，也就是递推。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010,mod=1e9+7;
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]=(ll)(c[i-1][j]+c[i-1][j-1])%mod;
}

int main(){
    init();
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",c[a][b]);
    }
    return 0;
}

时间复杂度 O(n^2) 。

Second time

1\leq n\leq 10000,1\leq b \leq a \leq 100000

此时发现，如果再用递推，则 O()=10^{10} ，显然超时，所以还要换种做法。

对于组合数来讲，还有一种性质：

C_n^m=\frac{n!}{m!\cdot (n-m)!}

那么不如来预处理 n!(n\in [0,100000]) ，但这时又有另一个问题，即

\frac{a}{b}\mod p \neq \frac{a \mod p}{b \mod p}

所以我们需要考虑模的逆元，解释略。

具体地讲，我们以fac[N],infac[N]表示数的阶乘和数阶乘的逆元，此时

b!=(b-1)!\cdot b, (b!)^{-1}=[(b-1)!\cdot b]^{-1}=[(b-1)!]^{-1}\cdot b^{-1}

即fac[i]=fac[i-1]*i%mod; infac[i]=infac[i-1]*qmi(i,mod-2,mod)%p;

此时问题全部解决，实践开始。

代码：

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

typedef long long ll;
const int N=1e5+10,mod=1e9+7;

int fac[N],infac[N];

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

void init(){
    fac[0]=infac[0]=1;
    for(int i=1;i<N;i++){
        fac[i]=(ll)fac[i-1]*i%mod;
        infac[i]=(ll)infac[i-1]*qmi(i,mod-2,mod)%mod;
    }
}

int main(){
    init();
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d",(ll)fac[a]*infac[b]%mod*infac[a-b]%mod);
    }
    return 0;
}

时间复杂度 O(n\cdot log_2n) 。

Third time

给定 n 组询问，每组询问给定三个整数 a ，b，p ，请你输出C_a^b\mod p 的值。
1\leq n\leq 20,1\leq b \leq a \leq 10^{18},1\leq p\leq 10^5

Lucas定理：C_a^b \equiv C_{a \mod p}^{b \mod p}\cdot C_{a/p}^{b/p} (\mod p)

（不要碰这玩意儿！！！）

代码：

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

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

int C(int a,int b,int p)//自变量类型int
{
    if(b>a)return 0;//漏了边界条件
    int res = 1;
    // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
    for(int i=1,j=a;i<=b;i++,j--)//i<=b而不是<
    {
        res = (LL)res*j%p;
        res = (LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}
//对公式敲
int lucas(LL a,LL b,int p)
{
    if(a<p && b<p)return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        LL a,b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a+b,a,p) << endl;
    }
    return 0;
}

Fourth time

询问给定两个整数 n ，m ，请你输出C_n^m 的值。

众所周知，高精度可以在不顾及时间的情况下解决任何计算量爆炸的问题。

从定义出发，C_a^b=\frac{(a-b+1)\cdot (a-b+2) ……(a-1)\cdot (a-2)\cdot a}{1\cdot2\cdot3 ……b}，直接算地话，我们需要用到大整数乘法和大整数除法，然而这么做的话既难写又慢，所以我们需要换种方式。

我们可以先把 C_a^b 分解质因数，再用大整数乘法。

如何分解质因数？

利用 C_n^m=\frac{n!}{m!\cdot (n-m)!} ，先分解分母再分解分子，次数相减，即得答案。

如何对 n! 分解质因数？

n!=1\cdot 2\cdot 3 ……n.

$\therefore n!=\prod\limits_{i=1}^{n}\prod\limits_{j=0}^{i}p_j^{a_j}

对于素数 p 来讲，在 1 ~ n 的表示中会重复 n 次，而真正的次数即 \lfloor\frac{n}{p}\rfloor ,而对于 p^2 来讲，同理得 \lfloor \frac{n}{p^2}\rfloor 。为什么 p^2 不会重复呢？注意这里是对 n! 分解质因数，而不是 n ，得到的次数不是 n 的表示中的，是 1 ~ n 的表示中的。

则对于每一个素数 p_i 来讲，其次数为 a_i=\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\lfloor\frac{n}{p^3}\rfloor+……+\lfloor\frac{n}{p^k}\rfloor(p^k\leq n)

理论可行，实践开始。

代码：

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

const int N=5010;

int primes[N],cnt;
int a[N];
bool st[N];

void get_primes(int x){
    for(int i=2;i<=x;i++){
        if(!st[i])  primes[cnt++]=i;
        for(int j=0;primes[j]<=x/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)  break;
        }
    }
}

int get(int n,int p){
    int res=0;
    while(n){
        res+=n/p;
        n/=p;
    }
    return res;
}

vector<int> mul(vector<int> a,int b){
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t){
        c.push_back(t%10);
        t/=10;
    }
    return c;
}

int main(){
    int n,m;
    cin>>n>>m;

    get_primes(n);

    for(int i=0;i<cnt;i++){
        int p=primes[i];
        a[i]=get(n,p)-get(m,p)-get(n-m,p);
    }

    vector<int> res;
    res.push_back(1);

    for(int i=0;i<cnt;i++)
        for(int j=1;j<=a[i];j++)
            res=mul(res,primes[i]);

    for(int i=res.size()-1;i>=0;i--)
        printf("%d",res[i]);
    puts(""); 
    return 0;
}