当前位置: 代码迷 >> 综合 >> 【逆元求组合数】
  详细解决方案

【逆元求组合数】

热度:45   发布时间:2024-01-18 01:41:43.0

求组合数C(n,m),并对(1e9+7)取余:

代码:

#include<cstdio>
typedef long long LL;
const LL MOD = 1e9 + 7;
LL fac[1000000+5];		//阶乘
LL inv[1000000+5];		//逆元 LL quickMod(LL a,LL b)
{LL ans = 1;while (b){if (b&1)ans = ans * a % MOD;a = a*a % MOD;b >>= 1;}return ans;
}void getFac()
{fac[0] = inv[0] = 1;for (int i = 1 ; i <= 1000000 ; i++){fac[i] = fac[i-1] * i % MOD;inv[i] = quickMod(fac[i],MOD-2);		//表示i的阶乘的逆元 }
}LL getC(LL n,LL m)		//C(n,m) = n!/((n-m)!*m!) % (1e9+7)
{return fac[n] * inv[n-m] % MOD * inv[m] % MOD;
}int main()
{getFac();int n,m;while (~scanf ("%d %d",&n,&m))printf ("%lld\n",getC((LL)n,(LL)m));return 0;
}


  相关解决方案