求组合数

组合数

从a个物品中挑选b个物品，共有几种选法。
题意不必解释，题型可以变化。

题型I

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

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤2000

• 题型分析
  此时a,b的大小都在2000以内，直接利用递推式
  C^b_a=C^{b-1}_ {a-1}+C^{b}_ {a-1}, 利用二维数组，
  计算量为 2000^2=4\times10^6 ,不会超时，时间复杂度为 O(n^2) 。

• 实现代码

#include <cstring>
#include <algorithm>

using namespace std;

const int N=2010;
typedef unsigned long long ULL;
ULL f[N][N];
const long long mod=1e9+7;

int main()
{
    int n;
    cin>>n;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<=i; j++)
        {
            if (!j)f[i][j]=1;
            else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
        }
    }

    while (n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<f[a][b]<<endl;
    }

    return 0;
}

题型II

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

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤10^5

• 题型分析
  与上题不同之处在于a,b的范围变大了，最大可到 10^5 ，此时再去用递推式显然会超时。此时要利用阶乘的定义来进行计算
  即 C^b_a=\frac{a!}{b!(a-b)!} 。
  当然这题没有这么简单，用阶乘直接去迭代或是递归都会超时。此时要引入逆元运算预处理，将除法转换为乘法。
  即 C^b_a=(a!)\times (b!)^{-1}\times[(a-b)!]^{-1}
  时间复杂度为 O(n\log n)

• 代码实现

// 1<=b<=a<=1e5

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 100010;

typedef long long ll;

ll fact[N], infact[N];

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 main()
{

    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
        infact[i] = (infact[i - 1]) * qmi(i, mod - 2, mod) % mod;   //求逆元
    }
    int n; cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        cout << fact[a] * infact[a - b] % mod * infact[b] % mod << endl;
    }
    return 0;
}

题型III

给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 C^b_a \mod p 的值。

输入格式
第一行包含整数 n,
接下来 n 行，每行包含一组 a,b,p。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤20,
1≤b≤a≤10^{18},
1≤p≤10^5,

• 题型分析
  此题的a,b的数据范围巨大，达到 10^{18},用上述的方法均会超时。
  此时可以引入卢卡斯定理：
  C^b_a=C^{b \mod p}_ {a \mod p} \times C^{b/p}_ {a/p} \mod p 。
  具体的证明过程可以百度一下 （实在是不好写。。。）
  这样就可以将数量级从 10^{18} 降至 10^5 左右，再利用题型II的做法，即可解决问题

• 具体代码

/*
1≤n≤20 ,
1≤b≤a≤1e18,
1≤p≤1e5,
*/

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

int p;


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 C(ll a, ll b)  //用逆元求阶乘
{
    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = (ll)res * j % p;
        res = (ll)res * qmi(i, 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;
}

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