青岛李沧区城乡建设局网站,六安马启兵,网站的主流趋势,谷歌云 wordpress组合数算法主要内容 一、基本思路1、组合数基本概念2、递推法——询问次数多 a b 值较小 模处理#xff08;%mod#xff09;3、预处理阶乘方法——询问次数较多 a b 值很大 模处理#xff08;%mod#xff09;4、卢卡斯定理——询问次数较少 #xff08;a b 值很大 a b 值较小 模处理%mod3、预处理阶乘方法——询问次数较多 a b 值很大 模处理%mod4、卢卡斯定理——询问次数较少 a b 值很大 mod模也很大5、分解质因数法无模直接求解——没有模运算 大数运算求解6、卡特兰数——多问题可转化为此问题 组合数求解 二、Java、C语言模板实现三、例题题解 一、基本思路
1、组合数基本概念
组合数排列组合中的组合数即给了a个人从中选b个问有多少种排列方方式 C b a C\begin{matrix} b \\ a \end{matrix} Cba公式如下
2、递推法——询问次数多 a b 值较小 模处理%mod
使用条件 1 - 10万组询问 1 ≤ b ≤ a ≤ 2000 公式如下 如何理解 在进行选择的时候包含需要的的一个已选一个 C b − 1 a − 1 C\begin{matrix} b-1 \\ a-1 \end{matrix} Cb−1a−1 在进行选择的时候不包含需要选的那个1个未选 C b a − 1 C\begin{matrix} b \\ a-1\end{matrix} Cba−1 两种情况相加即为递推公式即为所需内容。
3、预处理阶乘方法——询问次数较多 a b 值很大 模处理%mod
条件 1万次问询 1 ≤ b ≤ a ≤ 10^5 公式 分部求解 a阶乘求解 1/a-b! * b 已知 求解 注意此处如果 mod 是质数则可以使用快速幂进行逆元求解不是质数则需要使用扩展欧几里得算法进行逆元求解。 组合求解 总结 4、卢卡斯定理——询问次数较少 a b 值很大 mod模也很大
条件 20次询问 1 ≤ b ≤ a ≤ 10^18 1 ≤ p ≤ 10^5 定理 推导过程说实话没看懂感觉可以直接背过模板进行计算 5、分解质因数法无模直接求解——没有模运算 大数运算求解
公式 原理——分解质因数 大数运算求解 步骤 当我们需要求出组合数的真实值而非对某个数的余数时分解质因数的方式比较好用 筛法求出范围内的所有质数通过 C(a, b) a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p n / p^2 n / p^3 …用高精度乘法将所有质因子相乘 注意:说实话没怎么看懂我还是背模板吧
6、卡特兰数——多问题可转化为此问题 组合数求解
卡特兰数简介卡特兰数是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图和比利时的数学家欧仁·查理·卡特兰的名字来命名其前几项为从第0项开始1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … 卡特兰数结论 卡特兰数推导来自csdn作者你好世界wxx 首先我们需要将上述问题转换成一个等价的问题在一个二维平面内从(0, 0)出发到达(n, n)每次可以向上或者向右走一格0代表向右走一个1代表向上走一格则每条路径都会代表一个01序列则满足任意前缀中0的个数不少于1个数序列对应的路径则右下侧如下图 符合要求的路径必须严格在上图中红色线的下面不可以碰到图中的红线可以碰到绿线。则我们考虑任意一条不合法路径例如下图 补充 举例给定 n 个 0和 n 个 1它们将按照某种顺序排成长度为 2n 的序列求它们能排列成的所有序列中能够满足任意前缀序列中 0的个数都不少于 1 的个数的序列有多少个。输出的答案对 10^97取模。 注意 mod为质数进行逆元求解快速幂 mod非质数求解逆元扩展欧几里得算法
二、Java、C语言模板实现
递推法
// java 模板
static long[][] c new long[N][N];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] c[i - 1][j - 1]) % Mod; // c[i][j]实际上i是底数j是选取的数即 i a j b}}}}预处理方法
// java 模板
static int mod (int)(1e9 7);
static long[] fact new long[N]; // 使用 long 是为了防止爆 int
static long[] infact new long[N];static long qmi(long a, long k, long p){ // 快速幂求解逆元其中k mod - 2 使用费马定理求解逆元long res 1; while((k ! 0)){if((k 1) 1){res res * a % p;}k 1;a a * a % p;} return res;}static void init(){ // 对fact[] infact[] 两个数组进行预处理后面只需要简单计算即可以求出 fact[0] 1;infact[0] 1;for(int i 1; i N; i){fact[i] fact[i - 1] * i % mod; // a! 阶乘求解infact[i] infact[i - 1] * qmi(i, mod - 2, mod) % mod; // 1/(b!) 阶乘倒数求解}}// 组合数求解
long result (fact[a] * infact[b] % mod) * infact[a - b] % mod;卢卡斯定理
// java 模板
static long p;static long qmi(long a, long k){ // 快速幂求解long res 1;while(k ! 0){if((k 1) 1){res res * a % p;} k 1;a a * a % p;}return res;}static long C(long a, long b){
// 计算Cab用的是预处理阶乘的方法————此处后面还会常用一定要熟记是进行Cab求解重要方法long res 1;for(long i 1,j a; i b; i,j--){res res * j % p;res res * qmi(i , p - 2)% p; // qmi快速幂进行其中的逆元求解}return res;
}static long lucas(long a, long b){ // 卢卡斯定理求解 Cabif(a p b p){return C(a, b); // 不需要进行模处理直接就可以计算}return C(a % p, b % p) * lucas(a/p, b/p) % p; // 卢卡斯公式
}
分解质因数法无模直接求解
// java 模板
static int[] sum new int[N];
static int[] primes new int[N];
static boolean[] st new boolean[N];
static int cnt;//线性筛筛质数
static void get_primes(int x){for(int i2; ix; i){if(!st[i]) primes[cnt] i;for(int j0; primes[j]x/i; j){st[primes[j]*i] true;if(i%primes[j]0) break;}}
}//获得n!中某个质数的个数
static int get(int n, int p){int res 0;while(n!0){resn/p;n/p;}return res;
}// 主函数
get_primes(a);
for(int i0; icnt; i){int p primes[i];sum[i] get(a, p) - get(b, p) - get(a-b, p); // 最终得到质数个数
}BigInteger res new BigInteger(1); // 大数
for(int i0; i cnt; i){ // 质数个数int p primes[i];for(int j0; jsum[i]; j){res res.multiply(new BigInteger(String.valueOf(p))); // 阶乘求解}
}
卡特兰数
// Java模板
static long qmi(long a, long k){ // 快速幂求解质数逆元long res 1;while(k ! 0){if((k 1) 1){res res * a % mod;} k 1;a a * a % mod;} return res;}static long C(long a, long b){
// 此处求解 ab 范围不是很大的————组合数 % mod
// 假如ab范围更大的话则需要使用卢卡斯定理long res 1;for(long i 1, j a; i b;i, j--){res res * j % mod;res res * qmi(i , mod - 2) % mod;}return res;}// 主函数
// 可以用逆元来表示 (1/(n 1)!)
long result C(2 * n, n) * qmi(n 1, mod - 2) % mod ; // 此处用逆元来表示(1/(n 1)!)扩展欧几里得算法
import java.util.*;
public class Main{static int m (int) 1e9 7;public static int exgcd(int a,int b,int[] x,int[] y){ // 扩展欧几里得算法if(b 0){x[0] 1; y[0] 0;return a;}int d exgcd(b,a % b,y,x);y[0] - (a / b) * x[0] % m;return d;}public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt();//卡特兰数公式;c[2n][n] - c[2n][n-1] c[2n][n] / ( n 1)int a 2 * n;int b n;int[] x new int[1];int[] y new int[1];long res 1;for(int i a ;i a - b; i --) res res * i % m;for(int i 1 ; i n ; i ){exgcd(i,m,x,y);res ( res * x[0] % m m )% m;//同下}exgcd(n 1, m,x,y);//这里是因为有可能x[0]是系数所以有可能是负数所以模之后在加上一个m在模就可以得到正res (res * x[0] % m m) % m;System.out.println(res);}
}
C模板
// C 模板由yxc实现
1、递推法求组合数 —— 模板题 AcWing 885. 求组合数 I
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i 0; i N; i )for (int j 0; j i; j )if (!j) c[i][j] 1;else c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % mod;2、通过预处理逆元的方式求组合数 —— 模板题 AcWing 886. 求组合数 II
首先预处理出所有阶乘取模的余数fact[N]以及所有阶乘取模的逆元infact[N]
如果取模的数是质数可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板
{int res 1;while (k){if (k 1) res (LL)res * a % p;a (LL)a * a % p;k 1;}return res;
}// 预处理阶乘的余数和阶乘逆元的余数
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;
}3、Lucas定理 —— 模板题 AcWing 887. 求组合数 III
若p是质数则对于任意整数 1 m n有C(n, m) C(n % p, m % p) * C(n / p, m / p) (mod p)int qmi(int a, int k, int p) // 快速幂模板
{int res 1 % p;while (k){if (k 1) res (LL)res * a % p;a (LL)a * a % p;k 1;}return res;
}int C(int a, int b, int p) // 通过定理求组合数C(a, b)
{if (a b) return 0;LL x 1, y 1; // x是分子y是分母for (int i a, j 1; j b; i --, j ){x (LL)x * i % p;y (LL) y * j % p;}return x * (LL)qmi(y, p - 2, p) % p;
}int lucas(LL a, LL b, int p)
{if (a p b p) return C(a, b, p);return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}4、分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV
当我们需要求出组合数的真实值而非对某个数的余数时分解质因数的方式比较好用1. 筛法求出范围内的所有质数2. 通过 C(a, b) a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p n / p^2 n / p^3 ...3. 用高精度乘法将所有质因子相乘int primes[N], cnt; // 存储所有质数
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否已被筛掉void get_primes(int n) // 线性筛法求素数
{for (int i 2; i n; i ){if (!st[i]) primes[cnt ] i;for (int j 0; primes[j] n / i; j ){st[primes[j] * i] true;if (i % primes[j] 0) break;}}
}int get(int n, int p) // 求n中的次数
{int res 0;while (n){res n / p;n / p;}return res;
}vectorint mul(vectorint a, int b) // 高精度乘低精度模板
{vectorint c;int t 0;for (int i 0; i a.size(); i ){t a[i] * b;c.push_back(t % 10);t / 10;}while (t){c.push_back(t % 10);t / 10;}return c;
}get_primes(a); // 预处理范围内的所有质数for (int i 0; i cnt; i ) // 求每个质因数的次数
{int p primes[i];sum[i] get(a, p) - get(b, p) - get(a - b, p);
}vectorint res;
res.push_back(1);for (int i 0; i cnt; i ) // 用高精度乘法将所有质因子相乘for (int j 0; j sum[i]; j )res mul(res, primes[i]);5、卡特兰数 —— 模板题 AcWing 889. 满足条件的01序列
给定n个0和n个1它们按照某种顺序排成长度为2n的序列满足任意前缀中0的个数都不少于1的个数的序列的数量为 Cat(n) C(2n, n) / (n 1)三、例题题解 // java题解实现
// 递推法
import java.util.*;
import java.io.*;
public class Main{static int Mod (int)(1e9 7); // 此处的高次方值7要用括号括起来static int N 2010;static long[][] c new long[N][N];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] c[i - 1][j - 1]) % Mod; // c[i][j]实际上i是底数j是选取的数}}}}public static void main(String[] args) throws IOException {init();BufferedReader in new BufferedReader(new InputStreamReader(System.in));String str1 in.readLine();int n Integer.parseInt(str1);for(int i 0; i n; i){String[] str2 in.readLine().split( );int a Integer.parseInt(str2[0]);int b Integer.parseInt(str2[1]);System.out.println(c[a][b]);}}
}// 预处理方法求解组合数
import java.util.*;
import java.io.*;public class Main{static int N 100010; // 数据比较大使用此方法static int mod (int)(1e9 7);static long[] fact new long[N]; // 使用 long 是为了防止爆 intstatic long[] infact new long[N];static long qmi(long a, long k, long p){ // 快速幂求解逆元其中k mod - 2 使用费马定理求解逆元long res 1;while((k ! 0)){if((k 1) 1){res res * a % p;}k 1;a a * a % p;}return res;}static void init(){ // 对fact[] infact[] 两个数组进行预处理后面只需要简单计算即可以求出 fact[0] 1;infact[0] 1;for(int i 1; i N; i){fact[i] fact[i - 1] * i % mod; // a! 阶乘求解infact[i] infact[i - 1] * qmi(i, mod - 2, mod) % mod; // 1/(b!) 阶乘倒数求解}}public static void main(String[] args) throws IOException {BufferedReader in new BufferedReader(new InputStreamReader(System.in));String str1 in.readLine();int n Integer.parseInt(str1);init(); // 预处理阶乘数组while(n-- ! 0){String[] str2 in.readLine().split( );int a Integer.parseInt(str2[0]);int b Integer.parseInt(str2[1]);System.out.println((fact[a] * infact[b] % mod) * infact[a - b] % mod); // 组合数求解组合数公式得来}}
}// 卢卡斯定理需要解决的问题
// 1、问询次数很小
// 2、组合数中的a,b,p范围很大
import java.util.*;
import java.io.*;public class Main{static long p;static long qmi(long a, long k){ // 快速幂求解long res 1;while(k ! 0){if((k 1) 1){res res * a % p;}k 1;a a * a % p;}return res;}static long C(long a, long b){ // 计算Cab用的是预处理阶乘的方法long res 1;for(long i 1,j a; i b; i,j--){res res * j % p;res res * qmi(i , p - 2)% p; // qmi快速幂进行其中的逆元求解}return res;}static long lucas(long a, long b){ // 卢卡斯定理if(a p b p){return C(a, b); // 不需要进行模处理直接就可以计算}return C(a % p, b % p) * lucas(a/p, b/p) % p; // 卢卡斯公式}public static void main(String[] args) throws IOException {BufferedReader in new BufferedReader(new InputStreamReader(System.in));String str1 in.readLine();int n Integer.parseInt(str1);while(n-- ! 0){String[] str2 in.readLine().split( );long a Long.parseLong(str2[0]); // 此处是将String转换成long类型long b Long.parseLong(str2[1]);p Long.parseLong(str2[2]);System.out.println(lucas(a, b));}}
}// 分解质因数求解
import java.io.*;
import java.math.BigInteger;
import java.util.*;class Main{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;//线性筛筛质数static void get_primes(int x){for(int i2; ix; i){if(!st[i]) primes[cnt] i;for(int j0; primes[j]x/i; j){st[primes[j]*i] true;if(i%primes[j]0) break;}}}//获得n!中某个质数的个数static int get(int n, int p){int res 0;while(n!0){resn/p;n/p;}return res;}public static void main(String[]args)throws IOException{BufferedReader innew BufferedReader(new InputStreamReader(System.in));String[]arrin.readLine().split( );int aInteger.parseInt(arr[0]);int bInteger.parseInt(arr[1]);get_primes(a);for(int i0; icnt; i){int p primes[i];sum[i] get(a, p) - get(b, p) - get(a-b, p); // 最终得到质数个数}BigInteger res new BigInteger(1); // 大数for(int i0; i cnt; i){ // 质数个数int p primes[i];for(int j0; jsum[i]; j){res res.multiply(new BigInteger(String.valueOf(p))); // 阶乘求解}}System.out.println(res);}
} // 卡特兰数求解
import java.util.*;
import java.io.*;public class Main{static int mod (int)(1e9 7);static long qmi(long a, long k){ // 快速幂求解质数逆元long res 1;while(k ! 0){if((k 1) 1){res res * a % mod;}k 1;a a * a % mod;}return res;}static long C(long a, long b){ // 此处求解 ab 范围不是很大的————组合数 % mod// 假如ab范围更大的话则需要使用卢卡斯定理long res 1;for(long i 1, j a; i b;i, j--){res res * j % mod;res res * qmi(i , mod - 2) % mod;}return res;}public static void main(String[] args) throws IOException {BufferedReader in new BufferedReader(new InputStreamReader(System.in));int n Integer.parseInt(in.readLine());long result C(2 * n, n) * qmi(n 1, mod - 2) % mod ; // 此处用逆元来表示(1/(n 1))System.out.println(result);}
}
