|
前言
组合数就是
Cmn
C
n
m
，是排列组合中非常重要的一部分，最近做到了几道与计算组合数有关的题，想在此总结一下如何编程计算组合数。 某位大佬在我之前也写过类似的文章，这是他的博客：https://blog.csdn.net/u010582475/article/details/47707739
递推（杨辉三角）
先给出递推公式：
Cmn=Cmn−1+Cm−1n−1
C
n
m
=
C
n
−
1
m
+
C
n
−
1
m
−
1
证明：从n个数中选m个数，若第n个数不选，则相当于从n-1个数中选m个数，即
Cmn−1
C
n
−
1
m
；若第n个数选，则相当于从n-1个数中选m-1个数，即
Cm−1n−1
C
n
−
1
m
−
1
。那么总方案数即为两者之和。 当然，也可以根据组合数公式，展开来证明其相等，这里就不写出来了，有兴趣的话也可以自己去推。 如果写成数组形式，就是c[n][m]=c[n-1][m]+c[n-1][m-1]，这同时是杨辉三角的递推公式，所以组合数满足杨辉三角。边界是c[0][0]=1。若只要求一个组合数的话，也可以滚动一下这个数组，节约空间，但同时m这一维要倒着枚举，就像01背包一样。程序如下：
#include
using namespace std;
int n,m;
long long c[10005];
int main()
{
cin>>n>>m;
m=min(m,n-m);
c[0]=1;
for (int i=1;i=1;j--)
{
c[j]=c[j]+c[j-1];
}
}
coutm>>p;
cout=p的情况下使用的。这样可以减小n和m，使之小于p，再用乘法逆元去求组合数。 其实卢卡斯定理就是一个小优化，大部分和乘法逆元求组合数一样，不过要注意在n=0和m=0时的边界处理。
#include
using namespace std;
int n,m,p;
long long pow(long long x,long long y)
{
if (y==0) return 1;
long long z=pow(x,y/2)%p;
if (y%2==0) return z*z%p;
return z*z%p*x%p;
}
long long ni(long long x)
{
return pow(x,p-2);
}
long long c(int n,int m)
{
if (m==0) return 1%p;
if (n==0) return 0;
if (n>=p||m>=p) return c(n/p,m/p)*c(n%p,m%p)%p;//卢卡斯定理核心语句
long long x=1,y=1;
for (int i=n;i>=n-m+1;i--) x=x*i%p;
for (int i=1;i>n>>m>>p;
coutp;
m=min(m,n-m);//小优化
cout |