python求组合数的值、要求m和n从键盘输⼊_组合数
C（n,m）的四种求解⽅法
转⾃：⽂章
1、暴⼒求解
C(n,m)=n*(n-1)*...*(n-m+1)/m!，(n<=15)；
int CF(int n,int m)
{
int ans=,i,j;
for(i=n;i>=n-m+;i--)
ans*=i;
for(i=m;i>=;i--)
ans/=i;
return ans;
}
2、打表
C(n,m)=C(n-1,m-1)+C(n-1,m)，(n<=10000);
const int maxn = ;
const int MOD = ;
void CF(int n,int m)
{
int i,j;
for(i=;i<=maxn;i++)
{
c[][i]=;c[i][]=;
}
for(i=;i<=maxn;i++)
for(j=;j<=maxn;j++)
c[i][j]=(c[i-][j]+c[i-][j-])%MOD;
}
3、质因数分解
C(n,m)=n!/(m!*(n-m)!)，C(n,m)=p1a1-b1-c1p2a2-b2-c2…pkak-bk-ck,(n<=10000000)
#include
#include
#include
using namespace std;
const int MOD = ;
const int maxn = ;
bool a[maxn]={false};
vector prim_produce() //⽣成素数序列{
vector vc;
vc.push_back();
int i,j;
for(i=;i*i<=maxn;i+=)
{
if(!a[i])
{
vc.push_back(i);
for(j=i*i;j<=maxn;j+=i)
{
a[j]=true;
}
}
}
while(i
{
if(!a[i]) vc.push_back(i);
i+=;
}
return vc;
}
//计算n！素数p的指数
int cal(int x,int p)
{
int ans=;
long long re=p;
while(x>=re)
{
ans+=x/re;
re*=p;
}
return ans;
}
int Pow(long long n,int k) //⼆分求n的k次⽅
{
long long ans=;
while(k)
{
if(k&) ans=ans*n%MOD;
n=(n*n)%MOD;
k>>=;
}
return ans;
}
int comb(int n,int m) //计算公式
{
vector prim=prim_produce();
long long ans=;
int num;
for(int i=;i
{
num=cal(n,prim[i])-cal(m,prim[i])-cal(n-m,prim[i]); ans=(ans*Pow(prim[i],num))%MOD;
}
return ans;
}
int main(void)
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
printf("%d\n",comb(n,m));
}
return ;
}
4、Lucas定理
将m,n化为p进制，有:C(n,m)=C(n0,m0)*C(n1,m1)...(mod p)，算⼀个不是很⼤的C(n,m)%p,p为素数，化为线性同余⽅程,⽤扩展的欧⼏⾥德定理求解，n在int范围内，修改⼀下可以满⾜long long范围内。
#include
const int M = ;
int ff[M+]; //打表，记录n!，避免重复计算
//求最⼤公因数
int gcd(int a,int b)
{
if(b==)
return a;
else
return gcd(b,a%b);
}
//解线性同余⽅程，扩展欧⼏⾥德定理
int x,y;
void Extended_gcd(int a,int b)
{
if(b==)
{
x=;
y=;
}
else
{
Extended_gcd(b,a%b);
快速排序python实现
long t=x;
x=y;
y=t-(a/b)*y;
}
}
//计算不⼤的C(n,m)
int C(int a,int b)
{
if(b>a)
return ;
b=(ff[a-b]*ff[b])%M;
a=ff[a];
int c=gcd(a,b);
a/=c;
b/=c;
Extended_gcd(b,M);
x=(x+M)%M;
x=(x*a)%M;
return x;
}
//Lucas定理
int Combination(int n, int m) {
int ans=;
int a,b;
while(m||n)
{
a=n%M;
b=m%M;
n/=M;
m/=M;
ans=(ans*C(a,b))%M;
}
return ans;
}
int main()
{
int i,m,n;