数学知识：组合数（不同数据范围算法、满足条件的01序列）_综合

AcWing 885. 求组合数I

给定n组询问，每组询问给定两个整数a，b，请你输出C(a, b) mod (10⁹+7)的值。

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

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

数据范围
1≤n≤10000,
1≤b≤a≤2000
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1

Code:

#include <iostream>
#include <algorithm>
using namespace std;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] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}
}int main()
{
    int n;cin >> n;init();while(n --){
    int a, b;cin >> a >> b;cout << c[a][b] << endl;}return 0;
}

AcWing 886. 求组合数II

给定n组询问，每组询问给定两个整数a，b，请你输出C(a, b) mod (10⁹+7)的值。

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

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

数据范围
1≤n≤100000,
1≤b≤a≤2000
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1

求解组合数思路：
C(a,b) = a! /{ b! * (a - b)!}
取余运算不能相除，因此采用将相除转化为乘逆元的方法求解。
令fact数组为 i 的阶乘， infact数组为 i 的逆元的阶乘。
则C(a, b) = fact[a] *infact[b] *infact[a - b].

Code:

#include <iostream>
#include <algorithm>
using namespace std;typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int 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] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}int n;cin >> n;while(n --){
    int a, b;cin >> a >> b;cout <<(LL)fact[a] * infact[b] % mod * infact[a - b] % mod << endl;} return 0;
}

ACWing 887. 求组合数III

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

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

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

数据范围
1≤n≤20,
1≤b≤a≤10¹⁸,
1≤p≤10⁵,

输入样例：
3
5 3 7
3 1 5
6 4 13
输出样例：
3
3
2

Lucas定理：
若p是质数，则对于任意整数 1 ≤ m ≤ n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

Code:

#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 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) % 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, p) << endl;}return 0;
}

AcWing 888. 求组合数IV

输入a,b，求C(a, b)的值。
注意结果可能很大，需要使用高精度计算。

输入格式
共一行，包含两个整数a和b。

输出格式
共一行，输出Cba的值。

数据范围
1≤b≤a≤5000
输入样例：
5 3
输出样例：
10

分解质因数精确求组合数：
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
C(a, b) = a! /{b! * (a - b)!} = p1^a1p2^a2……pk^ak.
第一步：筛素数。把1~a的所有素数筛出来。
第二步：求每个素数出现的次数。n! 中p的次数是 n / p + n / p² + n / p³ + …
第三步：用高精度乘法把所有质因子相乘。

Code：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;const int N = 5010;
int primes[N], cnt, sum[N];
bool st[N];void get_primes(int n)
{
    for(int i = 2; i <= n; i ++){
    if(!st[i])  primes[cnt ++] = i;for(int j = 0; primes[j] <= n / 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() || t; i ++){
    if(i < A.size())  t += A[i]*b;C.push_back(t % 10);t /= 10;}while(C.back() == 0 && C.size() > 1)  C.pop_back();return C;
}int main()
{
    int a, b;cin >> a >> b;get_primes(a);for(int i = 0; i < cnt; i ++){
    int p = primes[i];sum[i] = get(a, p) - get(b, p) - get(a - b, p);}vector<int> res;res.push_back(1);for(int i = 0; i < cnt; i ++)for(int j = 0; j < sum[i]; j ++)res = mul(res, primes[i]);for(int i = res.size() - 1; i >= 0; i --)  cout << res[i];puts("");return 0;
}

AcWing 889. 满足条件的01序列

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

输入格式
共一行，包含整数n。

输出格式
共一行，包含一个整数，表示答案。

数据范围
1≤n≤10⁵
输入样例：
3
输出样例：
5

Code:
01 序列置于坐标系中，起点定于原点。若 0 表示向右走，1 表示向上走，任何前缀序列中 0 的个数不少于 1 的个数就转化为，路径上的任意一点，横坐标大于等于纵坐标。
任何一条从 (0,0) 走到 (n,n) 的不合法路径，都对应一条从 (0,0) 走到(n?1,n+1) 的一条路径。
最终结果为 C(2n, n) - C(2n, n + 1) = C(2n, n)/(n + 1)

#include <iostream>
using namespace std;const int mod = 1e9 + 7;
typedef long long LL;int qmi(int a , int k)
{
    int res = 1;while(k){
    if(k & 1) res = (LL)res * a % mod;k >>= 1;a = (LL) a * a % mod;}return res;
}int main()
{
    int n;cin >> n;int res = 1;for(int i = 2 * n ; i > n ; i--)res = (LL)res * i % mod;for(int i = n ; i > 0; i --) res = (LL) res * qmi(i , mod - 2) % mod;res = (LL) res * qmi(n + 1 , mod - 2) % mod;cout << res << endl;return 0;
}