【数学】求组合数的4种方法 |
您所在的位置：网站首页 › 阶乘简化计算公式 › 【数学】求组合数的4种方法 |
【数学】求组合数的4种方法
|
组合数公式：（图来自百度百科）
适用于\(C_a^b\)中\(a\) 和\(b\)不是很大的情况,一般\(1 \leq a,b \leq 10^4\) 所以可以直接预处理出来\(C_a^b\)，用的时候直接查表即可。 #include using namespace std; const int N = 2010, mod = 1e9 + 7; int c[N][N]; void init() { for(int i = 0; i < N; i ++ ) for(int j = 0; j >= 1; a = a * a % p; } return res; } int main() { //预处理阶乘和阶乘的逆元 fact[0] = infact[0] = 1; for(int i = 1; i < N; i ++) { fact[i] = (LL)fact[i - 1] * i % mod; infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod; //这里是关键，把组合数的公式转化为乘法形式 } int n; scanf("%d",&n); while(n --) { int a,b; scanf("%d%d",&a,&b); printf("%lld\n", (LL)fact[a] * infact[a - b] % mod * infact[b] % mod); //因为3个1e9级别的数相乘会爆longlong，所以乘了两个后要mod一下1e9+7，不影响结果 } return 0; } 3.Lucas定理求组合数此时\(1\leq a,b \leq 10^{18}\) Lucas定理：\(C_a^b \equiv C_{a \% p}^{b \% p} \cdot C_{a / p}^{b / p} (mod \ p)\) 中间组合数按定义算即可：\(C_a^b = \frac{a!}{(a-b)!\ b!}\) #include using namespace std; typedef long long LL; LL qmi(LL a,int k, int p) { LL res = 1; while(k) { if(k & 1) res = res * a % p; k >>= 1; a = a * a % p; } return res; } int C(int a,int b,int p) { if(a < b) return 0; LL res = 1; for(int i = 1, j = a; i > n; while(n --) { LL a,b; int p; cin >> a >> b >> p; cout = 0; i -- ) printf("%d", res[i]); puts(""); return 0; } 阶乘分解另外再补充一道阶乘分解，也需要用到分解质因数 #include #include #include #include using namespace std; const int N = 1e6 + 10; int primes[N], cnt; bool st[N]; void init(int n) { for(int i = 2; i |
【本文地址】
今日新闻 |
推荐新闻 |