求组合数
例题：
给定 n 组询问，每组询问给定两个整数 a，b请你输出 C a b mod(10^9^+7) 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000
1≤b≤a≤2000输入样例：
3 3 1 5 3 2 2输出样例：
3 10 1
一.递推式预处理
import java.util.Scanner;
public class Main {
static int N = 2010;
static int MOD = (int)1e9 + 10;
static int c[][] = new int[N][N];
public static void main(String[] args) {
init();
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(c[a][b]);
}
sc.close();
}
private static void init(){
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) c[i][j] = 1;
else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
}
}二.乘法逆元前缀乘处理
数据范围
1≤n≤10000
1≤b≤a≤10^5^
import java.util.Scanner;
public class Main {
static int N = (int)1e5 + 10;
static int MOD = (int)1e9 + 7;
static int fact[] = new int[N];
static int infact[] = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
init();
while (T -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println((long)fact[a] * infact[b] % MOD * infact[a - b] % MOD);
}
sc.close();
}
private static long qmi(long a,long b,long p){
long res = 1 % p;
while (b != 0){
if ((b & 1) == 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
private static void init(){
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (int)((long)(fact[i - 1] * i) % MOD);
infact[i] = (int)(infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD);
}
}
}三.lucas定理
结论：二项式系数Cnm可被素数 p 整除当且仅当在p进制表达下n的某一位的数值大于m对应位的数值。
例题：
给定 n 组询问，每组询问给定三个整数 a,b,p，其中 pp 是质数，请你输出 C b a mod p 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a,b,p
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤20
1≤b≤a≤10^18^
1≤p≤10^5^输入样例：
3 5 3 7 3 1 5 6 4 13输出样例：
3 3 2
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n -- > 0){
long a = sc.nextLong();
long b = sc.nextLong();
int p = sc.nextInt();
System.out.println(lucas(a, b, p));
}
sc.close();
}
private static int qmi(int a,int b,int p){
int res = 1;
while (b != 0){
if ((b & 1) == 1) res = (int)((long)res * a) % p;
a = (int)((long)a * a) % p;
b >>= 1;
}
return res;
}
private static int C(int a, int b, int p){
if (b > a) return 0;
int res = 1 % p;
for (int i = 1,j = a; i <= b; i++,j --) {
res = (int)((long)res * j) % p;
res = (int)((long)res * qmi(i, p - 2, p)) % p;
}
return res;
}
private static int lucas(long a, long b, int p){
if (a < p && b < p) return C((int)a, (int)b, p);
return (int)((long)C((int)a % p, (int)b % p, p) * lucas(a / p, b / p, p)) % p;
}
}四.对阶乘分解质因数 + 高精度
例题：
输入 a,b，求 Cba 的值。
注意结果可能很大，需要使用高精度计算。
输入格式
共一行，包含两个整数 a 和 b。
输出格式
共一行，输出 C b a 的值。
数据范围
1≤b≤a≤5000
输入样例：
5 3输出样例：
10
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
/*
* 分解质因数：
C[a][b] = p1^m1 * p2^m2 * … * pk^mk;其中p1~pk都是1~a中的素数；
m1~mk是其中对应的每个素数的次数，是在a中的次数 - b 中的次数 - (a - b)中的次数；
一个技巧就是获得a!的所有质因子，b!的所有质因子，(a-b)!的所有质因子，
然后用a的质因子的个数减去后两者质因子的个数，最后做一个高精度乘法就好了
*/
static int N=100010;
static int[] sum=new int[N];
static int[] primes=new int[N]; //存储所有质数
static boolean[] st=new boolean[N]; //代表这个数是否是质数
static int cnt; //存储质数的个数 从0开始
//线性筛选质数存储到primes[] 数组中
static void get_primes(int x) {
for (int i = 2; i <= x; i++) {
if(!st[i]) {
primes[cnt ++]=i;
}
for (int j = 0; primes[j] <= x / i; j++) {
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
//获取n!中质数的个数
// 6！阶乘中 质数2的个数
//比如 6 2 ==> res=4
static int get(int n,int p) {
int res = 0;
while(n != 0) {
res += n / p;
n /= p;
}
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
get_primes(a);
for (int i = 0; i < cnt; i++) {
int p = primes[i];
//然后用a的质因子的个数减去后两者质因子的个数
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
//将结果进行高精度乘法
//C[a][b] = p1^m1 * p2^m2 * … * pk^mk;其中p1~pk都是1~a中的素数；
BigInteger res = new BigInteger("1");
for (int i = 0; i < cnt; i++) {
int p = primes[i];
for (int j = 0; j < sum[i]; j++) {
res = res.multiply(new BigInteger(String.valueOf(p)));
}
}
System.out.println(res);
bufferedReader.close();
}
}卡特兰数
例题：
给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
输出的答案对 10^9^+7 取模。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1≤n≤10^5^
输入样例：
3输出样例：
5
import java.util.Scanner;
public class Main {
static int MOD = (int)1e9 + 7;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long res = 1;
for (int i = 1,j = 2 * n; i <= n; i ++, j --) {
res = res * j % MOD; //求2n*(2n-1)*(2n-2)*...*(2n-n+1)
res = res * qmi(i, MOD - 2, MOD) % MOD; //快速幂求n的阶乘的逆元
}
res = res * qmi(n + 1, MOD - 2, MOD) % MOD;
System.out.println(res);
sc.close();
}
private static long qmi(long a, long k, long m) {
long res = 1;
while(k != 0) {
if((k & 1) == 1) res = res * a % m;
a = a * a % m;
k >>= 1;
}
return res;
}
}