组合c(m,n)的计算方法 (一)

问题：求解组合数C(n,m)，即从n个相同物品中取出m个的方案数，由于结果可能非常大，对结果模10007即可。

方案1:

暴力求解，C(n,m)=n*(n-1)*...*(n-m+1)/m!，n<=15

[cpp]
int Combination(int n, int m)
{
const int M = 10007;
int ans = 1;
for(int i=n; i>=(n-m+1); --i)
ans *= i;
while(m)
ans /= m--;
return ans % M;
}

int Combination(int n, int m)
{
const int M = 10007;
int ans = 1;
for(int i=n; i>=(n-m+1); --i)
ans *= i;
while(m)
ans /= m--;
return ans % M;
}
方案2:

打表，C(n,m)=C(n-1,m-1)+C(n-1,m)，n<=10,000

[cpp]
const int M = 10007;
const int MAXN = 1000;
int C[MAXN+1][MAXN+1];
void Initial()
{
int i,j;
for(i=0; i<=MAXN; ++i)
{
C[0][i] = 0;
C[i][0] = 1;
}
for(i=1; i<=MAXN; ++i)
{
for(j=1; j<=MAXN; ++j)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % M;
}
}
int Combination(int n, int m)
{
return C[n][m];
}

const int M = 10007;
const int MAXN = 1000;
int C[MAXN+1][MAXN+1];
void Initial()
{
int i,j;
for(i=0; i<=MAXN; ++i)
{
C[0][i] = 0;
C[i][0] = 1;
}
for(i=1; i<=MAXN; ++i)
{
for(j=1; j<=MAXN; ++j)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % M;
}
}
int Combination(int n, int m)
{
return C[n][m];
}

方案3:

质因数分解，C(n,m)=n!/(m!*(n-m)!)，C(n,m)=p1a1-b1-c1p2a2-b2-c2…pkak-bk-ck,n<=10,000,000

[cpp]
#include
const int maxn=1000000;
#include
using namespace std;
bool arr[maxn+1]={false};
vector produce_prim_number()
{
vector prim;
prim.push_back(2);
int i,j;
for(i=3;i*i<=maxn;i+=2)
{
if(!arr[i])
{
prim.push_back(i);
for(j=i*i;j<=maxn;j+=i)
arr[j]=true;
}
}
while(i {
if(!arr[i])
prim.push_back(i);
i+=2;
}
return prim;
}
//计算n!中素数因子p的指数
int cal(int x,int p)
{
int ans=0;
long long rec=p;
while(x>=rec)
{
ans+=x/rec;
rec*=p;
}
return ans;
}
//计算n的k次方对m取模，二分法
int pow(long long n,int k,int M)
{
long long ans=1;
while(k)
{
if(k&1)
{
ans=(ans*n)%M;
}
n=(n*n)%M;
k>>=1;
}
return ans;
}
//计算C（n，m）
int combination(int n,int m)
{
const int M=10007;
vector prim=produce_prim_number();
long long ans=1;
int num;
for(int i=0;i {
num=cal(n,prim[i])-cal(m,prim[i])-cal(n-m,prim[i]);
ans=(ans*pow(prim[i],num,M))%M;
}
return ans;
}
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n),m&&n)
{
printf("%d\n",combination(m,n));
}
return 0;
}

#include
const int maxn=1000000;
#include
using namespace std;
bool arr[maxn+1]={false};
vector produce_prim_number()
{
vector prim;
prim.push_back(2);
int i,j;
for(i=3;i*i<=maxn;i+=2)
{
if(!arr[i])
{
prim.push_back(i);
for(j=i*i;j<=maxn;j+=i)
arr[j]=true;
}
}
while(i {
if(!arr[i])
prim.push_back(i);
i+=2;
}
return prim;
}
//计算n!中素数因子p的指数
int cal(int x,int p)
{