算法1
(暴力枚举) $O(n)$
初始化1-5000范围内的所有阶乘,然后套用组合数求解方式 $fact[a] / fact[a - b] / fact[b]$ 得解
时间复杂度
参考文献
JAVA 代码
import java.io.*;
import java.math.*;
public class Main {
static int N = 5010;
static BigInteger[] fact = new BigInteger[N];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
fact[1] = new BigInteger("1");
for (int i = 2; i < N; i++) {
fact[i] = fact[i - 1].multiply(new BigInteger(String.valueOf(i)));
}
String[] scan = br.readLine().split(" ");
int a = Integer.parseInt(scan[0], 10);
int b = Integer.parseInt(scan[1], 10);
bw.write(fact[a].divide(fact[a - b]).divide(fact[b]) + "\n");
bw.flush();
}
}