組合數(shù)：從個(gè)不同元素中取出
個(gè)元素的所有組合的個(gè)數(shù)，叫做從
個(gè)不同元素中取出
個(gè)元素的組合數(shù)。計(jì)算公式為：
- 性質(zhì)1：
- 性質(zhì)2：
第一種方法：打表
根據(jù)性質(zhì)2直接構(gòu)建一個(gè)的矩陣進(jìn)行計(jì)算：
public class Template {
static int mod = (int) 1e9 + 7;
static int max = 110;
static long[][] com = new long[max][max];
public static void main(String[] args) {
int n = 100, m = 30;
for (int i = 0; i < max; i++) {
com[i][0] = com[i][i] = 1;
for (int j = 1; j < i; j++) {
com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % mod;
}
}
System.out.println(com[n][m]);
}
}
空間復(fù)雜度：
預(yù)處理時(shí)間復(fù)雜度：，查詢時(shí)間復(fù)雜度：
第二種方法：階乘無模
根據(jù)組合的組合數(shù)的計(jì)算公式進(jìn)行：
public class Template {
static int mod = (int) 1e9 + 7;
static int max = 110;
static long[] fac = new long[max];
public static void main(String[] args) {
int n = 20, m = 10;
fac[0] = 1;
for (int i = 1; i < max; i++) {
fac[i] = (fac[i - 1] * i);
}
System.out.println(fac[n] / fac[m] / fac[n - m]);
}
}
空間復(fù)雜度：
預(yù)處理時(shí)間復(fù)雜度：濒旦，查詢時(shí)間復(fù)雜度：
由于涉及除法误墓，無法直接取模，所以引入乘法逆元出吹。
第三種方法：乘法逆元
逆元：對(duì)于和
（
和
互素），若
辙喂，則稱
的最小正整數(shù)解為
的逆元捶牢。
當(dāng)求解，如果知道
的逆元為
巍耗，那么可以轉(zhuǎn)化為
秋麸。暴力做法：
public class Template {
static int mod = (int) 1e9 + 7;
static int max = 110;
static long[] fac = new long[max];
static long[] inv = new long[max];
public static void main(String[] args) {
int n = 100, m = 30;
inv[0] = fac[0] = 1;
for (int i = 1; i < max; i++) {
fac[i] = (fac[i - 1] * i) % mod;
inv[i] = inv(fac[i]);
}
System.out.println(((fac[n] * inv[m]) % mod * inv[n - m]) % mod);
}
public static long inv(long a) {
for (int x = 1; x < mod; x++) {
if (a * x % mod == 1) return x;
}
return 0;
}
}
空間復(fù)雜度：
預(yù)處理時(shí)間復(fù)雜度：，其中
炬太，查詢時(shí)間復(fù)雜度：
第四種方法：乘法逆元+快速冪+階乘
費(fèi)馬小定理：對(duì)于a和素?cái)?shù)p灸蟆，滿足。
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=a%5E%7Bp-1%7D%3Da%5E%7Bp-2%7D*a" alt="a^{p-1}=a^{p-2}*a" mathimg="1">亲族，所以有炒考。根據(jù)逆元的定義可知，
是
的逆元霎迫。因此可以將求解逆元的問題轉(zhuǎn)換為
的快速冪問題票腰。
public class Template {
static int mod = (int) 1e9 + 7;
static int max = 110;
static long[] fac = new long[max];
static long[] inv = new long[max];
public static void main(String[] args) {
int n = 100, m = 30;
inv[0] = fac[0] = 1;
for (int i = 1; i < max; i++) {
fac[i] = (fac[i - 1] * i) % mod;
inv[i] = inv(fac[i]);
}
System.out.println(((fac[n] * inv[m]) % mod * inv[n - m]) % mod);
}
public static long pow(long a, long b) {
long ans = 1;
while (b > 0) {
if ((b & 1) == 1) ans = (ans * a) % mod;
a = a * a % mod;
b = b >> 1;
}
return ans;
}
public static long inv(long a) {
return pow(a, mod - 2);
}
}
空間復(fù)雜度：
預(yù)處理時(shí)間復(fù)雜度：，其中
女气，查詢時(shí)間復(fù)雜度為
