对于求C(n,m)
1.如果是对于小范围内的n和m（不是很难）就不说了
差不多用java的大数就可以了
2.当n在1e10^5范围左右，往往是会有取模，设这个数为mod（往往mod为质数，这个很重要）。
既然是组合数，就免不了有阶乘的部分，
n 的范围在10^5的数量级，所以完全可以线性扫一遍，用一个fac数组存i的阶乘对mod取模即可，
但是对于除法取模，必须得用到逆元，所以还是需要去求一下在一定范围内阶乘数对于mod的逆元，这里学习到了一个很巧妙的技巧，在这之前我们需要知道一个最大的阶乘数对于mod的逆元，由于是质数，我们可以运用费马小定理。
来看一下模板代码，这些可以看作是前期工作
long long fac[maxn],inv[maxn];//这里的maxn视具体数据范围而定
int n;
long long pow(long long x,int k)//快速幂，为求一个逆元而准备
{
long long ans=1;
while(k)
{
if(k&1)
ans=ans* x%mod;
x=x*x%mod;
k>>=1;
}
return ans;
}
void init()
{
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;//线性扫一遍求i的阶乘的逆元
inv[n]=pow(fac[n],mod-2);//求n的阶乘对于mod的逆元
for(int i=n-1;i>=1;i--)
inv[i]=inv[i+1]*(i+1)%mod;//这个技巧就是通过最大的n的阶乘的逆元来求所有小于n的阶乘的逆元，也是线性扫一遍
}
long long get(int n,int m)//然后直接用上面预处理的数组即可
{
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
//所有总的复杂度为o(n)
//这种情况对n在10^5左右是完全可以应付的，对于mod的大小范围没有太大要求只要是质数 3.n在10^9的数量级及以上，直接这样做就不行了，因为9次方的数组你是开不出来的，如果这个时候mod的范围是在10^5的范围差不多，这里就可以用Lucas定理，然后又可以转换成第二种的形式
long long Lucas(int n,int m)
{
if(m==0)return 1;
return get(m%mod,n%mod)*Lucas(n/mod,m/p);
}//需要注意的是打的表如fac和inv必须在1到mod的范围，这也是为什么mod的范围不能太大，不然又不能打表了。。。 4.n和mod的范围都非常大的情况还没有遇到过。。。
5.没有取模mod，但是n也不小，这种情况可以看一道题
**已知C(m,n) = m!/(n!(m-n)!)，输入整数p, q, r, s（p≥q，r≥s，p,q,r,s≤10000），计
算C(p,q)/C(r,s)。输出保证不超过10 8 ，保留5位小数。**
虽然结果是在int范围 内，但是中间结构可是要超long long的。
所以这个需要用到一个叫做唯一分解定理的东西。
实际是数的另一个表达方式，一个数一定能被若干的质数的乘积表示。
，所以我们需要先筛出1到10000的素数，放在prime这个素数表中，然后我们需要一个数组e来表示已在prime中的质数的幂，最后用一个pow函数去求即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include <algorithm>
#include<cmath>
#include<vector>
using namespace std;
vector<int> prime;
bool a[10005];
int e[10005];
void getPrime(int n)//upper bound
{
memset(a,true,sizeof(a));
memset(e,0,sizeof(0));
for(int i=2;i<=n;i++)
{
if(a[i])
{
prime.push_back(i);
for(int j=i+i;j<=n;j+=i)
a[j]=false;
}
}
}
void addNum(int x,int d)
{
int t=0;
while(x!=1)
{
if(x%prime[t]==0)
e[t]+=d,x/=prime[t];
else
t++;
}
}
void addFac(int x,int d)
{
for(int i=2;i<=x;i++)
addNum(i,d);
}
int main()
{
getPrime(10000);
int p,q,r,s;
cin>> p>>q>>r>>s;
addFac(p,1);
addFac(q,-1);
addFac(p-q,-1);
addFac(r,-1);
addFac(s,1);
addFac(r-s,1);
double ans=1;
for(int i=0;i<prime.size();i++)
{
if(e[i]!=0)
ans*=pow(prime[i],e[i]);
}
printf("%.5lf",ans);
return 0;
}
//但是对于n的数量级在大一些的情况，就不行了，这个时间复杂度为o(nlogn)
转自：国特震哥：https://blog.csdn.net/Coldfresh/article/details/72871167
京公网安备 11010502036488号