文章目录
- 💬前言
- 885. 求组合数 I C(m,n) 【dp】
- 886 求组合数 II 【数据大小10万级别】 【费马小定理+快速幂+逆元】
- 887. 求组合数 III 【le18级别】 【卢卡斯定理 + 逆元 + 快速幂 】
- 888.求组合数 IV 【没有%p -- 高精度算出准确结果】 【分解质因数 + 高精度乘法 --只用一次高精度提高运行效率】
- 889.满足条件的01序列 【卡特兰数-用法极多！】
💬前言
💡本文以组合数多种写法，按不同数据范围结合不同数论知识的组合数末班
组合数是高频的数论考点，掌握组合数是必要的！
如果对您有帮助的话还请动动小手 点赞👍，收藏⭐️，关注❤️
组合数公式：百度文库链接
885. 求组合数 I C(m,n) 【dp】
题目描述 ：
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C(b,a) mod (109+7) 的值。
数据范围 ：
1 ≤ n≤10000,
1 ≤ b ≤ a ≤ 2000 【审题C(b,a) a >= b】
输入输出格式 ：
输入
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出
共 n 行，每行输出一个询问的解。
输入输出样例 ：
输入
3
3 1
5 3
2 2
输出
3
10
1
思路：DP递推式预处理 C(a,b)
C(a,b) = C(a-1,b) + C(a-1,b-1)
选苹果 - 分类 – 每个包含/不包含
【到a的情况对一个未选择的苹果有两种结果，第a个选它，或不选它，选其他的（那么就要从它之外的再选一个）】
[离散数学-接近实际问题-离散-高等代数 - 数学分析 - 均需三学期 ！！！]
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; //定义： C(a,0) = 1
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1] % mod); //DP 选/不选
}
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;
}
886 求组合数 II 【数据大小10万级别】 【费马小定理+快速幂+逆元】
题目描述：
给定n组询问，每组询问给定两个整数a，b，请你输出C(a,b) mod (10^9+7)的值。
输入格式
第一行包含整数n。接下来n行，每行包含一组a和b。
输出格式
共n行，每行输出一个询问的解。
数据范围
1≤n≤100000,1≤b≤a≤105
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
思路： 【即C(a,b)[a>=b]组合公式展开 —> C(a-1,b) * C(a-1,b-1) ，分别求分母和分子】
结合代码：
fact[i] = i! % p;
infact[i] = (i!)的逆元 % p 【除 ==> 乘逆元（快速幂 – 费马小定理）】 【分母 】
C( a , b ) % p = fact[a % p] % p * infact[b - a] % p * infact[b] % p
C a b = a ! b ! ( a − b ) ! C^b_a = \dfrac{a!}{b!(a-b)!} Cab=b!(a−b)!a!
typedef long long LL;
const int N = 100010,mod = 1e9 + 7;
int fact[N],infact[N]; //i! :阶乘 ， i阶乘的逆元 : infact[i]
int qmi(int a,int k,int p) //数值大就LL 一般都是!!!
{
int res = 1; //乘除法的初始值
while(k)
{
if(k % 2) res = (LL)res * a % p; //强转 也可以k & 1 表示奇数就行
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;//i的阶乘
infact[i] = (LL)infact[i - 1] * qmi(i,mod - 2,mod) % mod; //a % p 的逆元 的幂 = p-2 ，a逆为a^p-2^
}
int n;
scanf("%d",&n);
while(n --)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",(LL)fact[a] * infact[b] % mod * infact[a - b] % mod); //%f等于0原因分母求解过程中0，后一直为0，最后相乘结果为0
}
return 0;
}
887. 求组合数 III 【le18级别】 【卢卡斯定理 + 逆元 + 快速幂 】
给定n组询问，每组询问给定三个整数a,b,p，其中p是质数，请你输出C b上a下 mod p的值。
输入格式
第一行包含整数n。
接下来n行，每行包含一组a,b,p。
输出格式
共n行，每行输出一个询问的解。
数据范围
1≤n≤20,
1≤b≤a≤1e18,
1≤p≤105,
输入样例：
3
5 3 7
3 1 5
6 4 13
输出样例：
3
3
2
解题思路：
a和b的取值到了1018 改用：
卢卡斯定理： C ( a , b ) % p = C( a%p , b%p ) * C( a/p , b/p ) % p ; （p为质数）
#include<algorithm>
typedef long long LL;
int p;
int qmi(int a,int k) //p是全局变量不用传进来，直接用
{
int res = 1;
while(k)
{
if(k % 2) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
//特别注意题目给定输入的a，b顺序
int C(int a,int b) //组合数 C(a,b) == b! / (a-b)! * a! ********
{
int res = 1;
for(int i = 1,j = a ;i <= b;i++,j--) // i为b! ,j = a! ,qmi求i逆元 为
{
res = (LL)res * j % p; //除 ， 乘上i的逆元
res = (LL)res * qmi(i,p-2) % p;
}
return res;
}
int lucas(LL a,LL b) //递归 //传进的数是LL类型
{
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;
}
}
888.求组合数 IV 【没有%p – 高精度算出准确结果】 【分解质因数 + 高精度乘法 --只用一次高精度提高运行效率】
较难
题目描述：
输入a,b，求C(a,b)的值。注意结果可能很大，需要使用高精度计算。 【a >= b】
输入格式
共一行，包含两个整数a和b。
输出格式
共一行，输出C(a,b)的值。
数据范围
1≤b≤a≤5000
输入样例：
5 3
输出样例：
10
*公式：C(a,b) = a! / ( b! (a - b)! ) 【a >= b】
一般的处理方式：先把C(a,b)分解质因数，变成只有乘法的形式 --只要高精度乘法 -优化运算速度
质因子p个数运算： 分母里面的有多少个p， - 分子里的多少个p ，差值就是个数
阶乘当中包含p的个数 a! = 向下取整a/p1 [p1为p的倍数] +向下取整a/p2 [p2为p2的倍数] +向下取整a/p3 + …
质数的次数【p的各种倍数中拿出一个p 得出所有含有p的项中，p的总个数】【如p的k次方被加k次，不重复不漏算 】
#include<vector>
const int N = 5010;
int primes[N],cnt;
bool st[N];
int sum[N];
void get_primes(int n) //线性筛法
{
for(int i = 2;i <= n;i++)
{
if(!st[i]) primes[cnt ++] = i;//没有标记，需遍历i的质数的倍数 ，筛除 [第一次i为2，是质数先放入，后面3,5同理，4就被筛掉了]
for(int j = 0 ;primes[j] <= n / i;j++) //遍历到 i == sqrt(n)
{
st[primes[j] * i] = true; //筛除i的质数的倍数，
if(i % primes[j] == 0) break; // i是pj 的倍数时，后面已经筛选完了，都是倍数，就不用继续了，结束
}
}
}
int get(int n,int p) //质因数n的个数
{
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)//t == 0结束
{
c.push_back( t % 10);
t /= 10;
}
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]); // (res = 1) * primes[i] 的^sum[i]^次方
for(int i = res.size() - 1;i >= 0;i --) printf("%d", res[i]);//vector遍历输出
puts("");
return 0;
}
889.满足条件的01序列 【卡特兰数-用法极多！】
题目描述：
给定n个0和n个1，它们将按照某种顺序排成长度为2n的序列，求它们能排列成的所有序列中，
能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。输出的答案对10^9+7取模。
输出格式
共一行，包含整数n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1≤n≤105
输入样例：
3
输出样例：
5
思路
路径转换成一个排列 ，如坐标从（0,0）开始走，0向右走，1向上走，到终点得到一个序列
当要求能走的坐标满足x >= y 时，ans = = 即所有不经过y = x + 1这条边的数 = = 所有走法 - 经过y = x + 1这条边的数
如(0,0)- - >(6,6) 必走12步且选6步向上走 y = x + 1等效，即C(12,6) - C(12,5)
扩展推： (0,0) 到 (n,n) 且不经过y = x + 1 即
Cat(n) = C(n+n , n) - C(n+n , n-1) = C(2*n,n) / (n + 1) 【卡特兰数】
【卡特兰数应用：栈的合法序列，括号匹配数量…
简记： qmi(x的逆元) ，在%p条件下可以表示为 1 / x
main :
①②求C(2n,n) ①先求 a! / (a-b)!
for(int i = a;i > a - b;i --) res = (LL)res * i % mod; //a! / (a-b)!
②再求 1 / b!
for(int i = 1;i <= b;i ++) res = (LL)res * qmi(i,mod - 2,mod) % mod;
③最后再乘 1 / (n+1) 【用 n+1 的逆元表示】
res = (LL)res * qmi(n + 1,mod - 2,mod) % mod;
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;//取模为质数
//因为%p所以都可以int
ll qmi(int a,int k,int p) //如果p不是质数，那么逆元只能用扩展欧几里得定理求！！！
{
int res = 1;
while(k)
{
if(k % 2) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
int n;
cin >> n;
int a = 2 * n , b = n;
int res = 1;
//求C(2*n,n) = a! / b!(a-b)! 【C(a,a-b) * b!逆元（分母）】
for(int i = a;i > a - b;i --) res = (LL)res * i % mod; //a! / (a-b)!
for(int i = 1;i <= b;i ++) res = (LL)res * qmi(i,mod - 2,mod) % mod;
//C(2*n,n) / (n+1)
res = (LL)res * qmi(n + 1,mod - 2,mod) % mod; // 乘(n+1) 逆元 == 1/(n+1) % p
cout << res << endl;
return 0;
}
一篇不同代码的卡特兰数01序列
【其他代码-dp法参考】
卡特兰数 ： C a t ( n ) = C 2 n n ( n + 1 ) Cat(n) = \frac{C_{2n}^n}{(n + 1)} Cat(n)=(n+1)C2nn
带入试试是否满足样例！
卡特兰数的简单代码实现 【DP】
组合数dp法求卡特兰数
c[a][b]仅能求 1 <= a,b <= 2000
C
a
t
(
n
)
=
C
2
n
n
−
C
2
n
n
−
1
=
C
2
n
n
n
+
1
Cat(n)= {C_{2n}^n} - {C_{2n}^{n-1}} = \dfrac{C_{2n}^n}{n+1}
Cat(n)=C2nn−C2nn−1=n+1C2nn
const int N = 1e4+10;
int c[N][N]; //存组合数 c[a][b] 表示从a个苹果中选b个的方案数 【a >= b】
void init() //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; //逆推，取第b个时是最后一个还是前面的（最后一个取/不取）
}
int main()
{
cin >> n;
cout << c[2*n][n] / (n+1) ;
return 0;
}
分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
1. 筛法求出范围内的所有质数
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + …
3. 用高精度乘法将所有质因子相乘
