组合数公式用C语言怎么算,求组合数C（m,n）的多种计算方法
https://ac.nowcoder.com/discuss/187813?type=101&order=0&pos=1&page=0
https://blog.csdn.net/shadandeajian/article/details/82084087
1.简单法---适合n,m很小
#includeusing namespacestd;const int MAXN = 1000;int C[MAXN+1][MAXN+1];//求排列组合数C(m,n) 上面为m,下面为n m//C(m,n)=n!/m!/(n-m)!=n*(n-1)*..*(n-m+1)/m!.
int baoli_C(int m,int n) //暴力法这里n<=15
{int summ=1,sumn=1;//其实算C(m,n)只要计算min(m,n-m)次就可以了
if(m>n-m)
m=n-m;for(int i=1;i<=m;i++){
summ*=i;
sumn=sumn*(n-i+1);
}return sumn/summ;
}void dabiao_C(){ //打表，数据为int,注意溢出数据 n<60//C(n, m) = C(n -1, m - 1) + C(n - 1, m)
for(int i=0;i)
{//C[i][0]=1; C[0][i]=0;//该写法顺序是错误的，因为这样写C[0][0]=0;
C[0][i]=0;C[i][0]=1;
}for(int i=1;i)
for(int j=1;j)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}intmain(){
dabiao_C();intm,n;while(cin>>m>>n){ //mcout
}
}
2.Lucas定理求组合数
组合数C(n, m) % p
= (n!/m!/(n-m)!)%mod 组合数公式
= n!*inv(m!*(n-m)!)%mod 转化式子
= n!*(m!*((n-m)!)^(mod-2))%mod 由于p是素数，有费马小定理可知，m! * (n - m)! 关于p的逆元就是m! * (n - m)!的p-2次方。
=(n*(n-1)*..*(n-m+1) / m!) %mod.==( (n*(n-1)*..*(n-m+1)) * (m^(mod-2)) ) %mod.
第一种情况：p是素数，且p较小，采用打表---打表记录 阶乘%mod的值 --- n!*(m!*((n-m)!)^(mod-2))%mod
#includeusing namespacestd;#define ll long long
const int MAXN = 1000;#define mod 998244353
const int maxn = 1e5+10;
ll fac[maxn];//maxn应该小于1e5,这样Lucas定理才适用
void Init(){ //对阶乘打表
fac[0]=1;for(int i=1;i<=maxn-5;i++){
fac[i]=fac[i-1]*i%mod;
}
}
ll quickpow(ll a,ll b){
ll t=a,ans=1;while(b!=0){if(b&1==1)
ans=(ans*t)%mod;
t=t*t%mod;
b>>=1;
}return ans%mod;
}
ll C(ll n,ll m){if(m>n)return 0;return fac[n]*quickpow(fac[m]*fac[n-m],mod-2)%mod;
}
ll Lucas(ll n,ll m){if(m==0)return 1;return Lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}intmain(){
ll n,m;
Init();while(cin>>n>>m){
cout
}
}
第二种情况：p是素数，且p比较大，不好打表 ---(n*(n-1)*..*(n-m+1) / m!) %mod.
#includeusing namespacestd;#define ll long long
const int MAXN = 1000;#define mod 998244353ll pow(ll a, ll b, ll m)
{
ll ans= 1;
a%=m;while(b)
{if(b & 1)ans = (ans % m) * (a % m) %m;
b/= 2;
a= (a % m) * (a % m) %m;
}
ans%=m;returnans;
}
ll inv(ll x, ll p)//x关于p的逆元，p为素数
{return pow(x, p - 2, p);
}
ll C(ll n, ll m, ll p)//组合数C(n, m) % p = (n!/m!/(n-m)!)%mod = n!*inv(m!*(n-m)!)%mod = n!*(m!*((n-m)!)^(mod-2))%mod
{if(m > n)return 0;
ll up= 1, down = 1;//分子分母;
for(int i = n - m + 1; i <= n; i++)up = up * i %p;for(int i = 1; i <= m; i++)down = down * i %p;return up * inv(down, p) %p;
}
ll Lucas(ll n, ll m, ll p)
{if(m == 0)return 1;return C(n % p, m % p, p) * Lucas(n / p, m / p, p) %p;
}intmain(){intm,n;while(cin>>m>>n){ //mcout
}
}
第三种情况：p不是素数，且n,m比较大---扩展Lucas定理：https://www.cnblogs.com/fzl194/p/9095177.html
#includeusing namespacestd;
typedeflong longll;const int maxn = 1e6 + 10;const int mod = 1e9 + 7;
ll pow(ll a, ll b, ll m)
{
ll ans= 1;
a%=m;while(b)
{if(b & 1)ans = (ans % m) * (a % m) %m;
b/= 2;
a= (a % m) * (a % m) %m;
}
ans%=m;returnans;
}
ll extgcd(ll a, ll b, ll& x, ll&y)//求解ax+by=gcd(a, b)//返回值为gcd(a, b)
{
ll d=a;if(b)
{
d= extgcd(b, a %b, y, x);
y-= (a / b) *x;
}else x = 1, y = 0;returnd;
}
ll mod_inverse(ll a, ll m)//求解a关于模上m的逆元//返回-1表示逆元不存在
{
ll x, y;
ll d=extgcd(a, m, x, y);return d == 1 ? (m + x % m) % m : -1;
}
ll Mul(ll n, ll pi, ll pk)//计算n! mod pk的部分值 pk为pi的ki次方//算出的答案不包括pi的幂的那一部分
{if(!n)return 1;
ll ans= 1;if(n /pk)
{for(ll i = 2; i <= pk; i++) //求出循环节乘积
if(i % pi)ans = ans * i %pk;
ans= pow(ans, n / pk, pk); //循环节次数为n / pk
}for(ll i = 2; i <= n % pk; i++)if(i % pi)ans = ans * i %pk;return ans * Mul(n / pi, pi, pk) % pk;//递归求解
}
ll C(ll n, ll m, ll p, ll pi, ll pk)//计算组合数C(n, m) mod pk的值 pk为pi的ki次方
{if(m > n)return 0;
ll a= Mul(n, pi, pk), b = Mul(m, pi, pk), c = Mul(n -m, pi, pk);
ll k= 0, ans;//k为pi的幂值
for(ll i = n; i; i /= pi)k += i /pi;for(ll i = m; i; i /= pi)k -= i /pi;for(ll i = n - m; i; i /= pi)k -= i /pi;
ans= a * mod_inverse(b, pk) % pk * mod_inverse(c, pk) % pk * pow(pi, k, pk) % pk;//ans就是n! mod pk的值
ans = ans * (p / pk) % p * mod_inverse(p / pk, pk) % p;//此时用剩余定理合并解
returnans;
}
ll Lucas(ll n, ll m, ll p)
{
ll x=p;
ll ans= 0;for(ll i = 2; i <= p; i++)
{if(x % i == 0)
{
ll pk= 1;while(x % i == 0)pk *= i, x /=i;
ans= (ans + C(n, m, p, i, pk)) %p;
}
}returnans;
}intmain()
{
ll n, m, p;while(cin >> n >> m >>p)
{
cout
}
return 0;
}
#includeusing namespace std;
#define mod 998244353
#define ll long long
ll fac[100005];
void Init(){
fac[0]=1;
for(int i=1;i<=100000;i++)
fac[i]=(fac[i-1]*i)%mod;
}
long long quickmod(int x,int y)
{
if(x==0)
return 0;
long long t=x,ans=1;
while(y!=0)
{
if(y&1==1)
ans=(ans*t)%mod;
t=(t*t)%mod;
y>>=1;
}
return ans;
}
ll C(int n,int m){
return fac[n]/fac[n-m]*quickmod(fac[m],mod-2)%mod;
}
ll Lucas(int n,int m){
if(m==0)
return 1;
return Lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
int main()
{
Init();
int T;
scanf("%d",&T);
int a,b,n,m;
while(T--){
scanf("%d%d%d%d",&a,&b,&n,&m);
long long h,ans;
h=Lucas(n-1,m-1);
// cout/ cout
cout
}
/*
10
2 0 5 3
2 3 3 5
5 1 4 6
5 1 6 4
0 2 6 4
2 0 6 4
*/