麻涌镇网站建设,如何开发网站建设业务,seo全网推广营销软件,推荐一个国外好的网站模板文章目录#x1f4ac;前言885. 求组合数 I C(m,n) 【dp】886 求组合数 II 【数据大小10万级别】 【费马小定理快速幂逆元】887. 求组合数 III 【le18级别】 【卢卡斯定理 逆元 快速幂 】888.求组合数 IV 【没有%p -- 高精度算出准确结果】 【分解质因数 高精度乘法 --只用一…
文章目录前言885. 求组合数 I C(m,n) 【dp】886 求组合数 II 【数据大小10万级别】 【费马小定理快速幂逆元】887. 求组合数 III 【le18级别】 【卢卡斯定理 逆元 快速幂 】888.求组合数 IV 【没有%p -- 高精度算出准确结果】 【分解质因数 高精度乘法 --只用一次高精度提高运行效率】889.满足条件的01序列 【卡特兰数-用法极多】卡特兰数 Cat(n)C2nn(n1)Cat(n) \frac{C_{2n}^n}{(n 1)}Cat(n)(n1)C2nn前言 本文以组合数多种写法按不同数据范围结合不同数论知识的组合数末班 组合数是高频的数论考点掌握组合数是必要的 如果对您有帮助的话还请动动小手 点赞收藏⭐️关注❤️ 组合数公式百度文库链接 885. 求组合数 I C(m,n) 【dp】 题目描述 给定 n 组询问每组询问给定两个整数 ab请你输出 C(b,a) mod (1097) 的值。 数据范围 1 ≤ n≤10000, 1 ≤ b ≤ a ≤ 2000 【审题C(b,a) a b】 输入输出格式 输入 第一行包含整数 n。 接下来 n 行每行包含一组 a 和 b。 输出 共 n 行每行输出一个询问的解。 输入输出样例 输入 3 3 1 5 3 2 2 输出 3 10 1 思路DP递推式预处理 C(a,b) C(a,b) C(a-1,b) C(a-1,b-1) 选苹果 - 分类 – 每个包含/不包含 【到a的情况对一个未选择的苹果有两种结果第a个选它或不选它选其他的那么就要从它之外的再选一个】 [离散数学-接近实际问题-离散-高等代数 - 数学分析 - 均需三学期 ] 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 i;j )if(!j) c[i][j] 1; //定义 C(a,0) 1 else c[i][j] (c[i - 1][j] c[i - 1][j - 1] % mod); //DP 选/不选
} int main()
{init();int n;scanf(%d,n);while(n --){int a,b;scanf(%d%d,a,b);printf(%d\n,c[a][b]);}return 0;
}
886 求组合数 II 【数据大小10万级别】 【费马小定理快速幂逆元】 题目描述 给定n组询问每组询问给定两个整数ab请你输出C(a,b) mod (10^97)的值。 输入格式 第一行包含整数n。接下来n行每行包含一组a和b。 输出格式 共n行每行输出一个询问的解。 数据范围 1≤n≤100000,1≤b≤a≤105 输入样例 3 3 1 5 3 2 2 输出样例 3 10 1 思路 【即C(a,b)[ab]组合公式展开 — C(a-1,b) * C(a-1,b-1) 分别求分母和分子】 结合代码 fact[i] i! % p; infact[i] (i!)的逆元 % p 【除 乘逆元快速幂 – 费马小定理】 【分母 】 C( a , b ) % p fact[a % p] % p * infact[b - a] % p * infact[b] % p Caba!b!(a−b)!C^b_a \dfrac{a!}{b!(a-b)!} Cabb!(a−b)!a!
typedef long long LL;
const int N 100010,mod 1e9 7;int fact[N],infact[N]; //i! :阶乘 i阶乘的逆元 : infact[i]int qmi(int a,int k,int p) //数值大就LL 一般都是!!!
{int res 1; //乘除法的初始值 while(k){if(k % 2) res (LL)res * a % p; //强转 也可以k 1 表示奇数就行 a (LL)a * a % p;k 1;}return res;
}int main()
{fact[0] infact[0] 1; //乘除法的初始值 for(int i 1;i N;i){fact[i] (LL)fact[i - 1] * i % mod;//i的阶乘 infact[i] (LL)infact[i - 1] * qmi(i,mod - 2,mod) % mod; //a % p 的逆元 的幂 p-2 a逆为a^p-2^ }int n;scanf(%d,n);while(n --){int a,b;scanf(%d%d,a,b);printf(%d\n,(LL)fact[a] * infact[b] % mod * infact[a - b] % mod); //%f等于0原因分母求解过程中0后一直为0最后相乘结果为0 }return 0;
}
887. 求组合数 III 【le18级别】 【卢卡斯定理 逆元 快速幂 】 给定n组询问每组询问给定三个整数a,b,p其中p是质数请你输出C b上a下 mod p的值。 输入格式 第一行包含整数n。 接下来n行每行包含一组a,b,p。 输出格式 共n行每行输出一个询问的解。 数据范围 1≤n≤20, 1≤b≤a≤1e18, 1≤p≤105, 输入样例 3 5 3 7 3 1 5 6 4 13 输出样例 3 3 2 解题思路 a和b的取值到了1018 改用 卢卡斯定理 C ( a , b ) % p C( a%p , b%p ) * C( a/p , b/p ) % p ; p为质数 #includealgorithmtypedef long long LL;
int p;int qmi(int a,int k) //p是全局变量不用传进来直接用
{int res 1;while(k){if(k % 2) res (LL)res * a % p;a (LL)a * a % p; k 1;}return res;
}
//特别注意题目给定输入的ab顺序
int C(int a,int b) //组合数 C(a,b) b! / (a-b)! * a! ********
{int res 1;for(int i 1,j a ;i b;i,j--) // i为b! ,j a! ,qmi求i逆元 为 {res (LL)res * j % p; //除 乘上i的逆元 res (LL)res * qmi(i,p-2) % p; }return res;
}int lucas(LL a,LL b) //递归 //传进的数是LL类型
{if(a p b p) return C(a,b);return (LL)C(a % p,b % p) * lucas(a / p, b / p) % p;
}int main()
{int n;cin n;while(n --){LL a, b;cin a b p ;cout lucas(a,b) endl; }
}888.求组合数 IV 【没有%p – 高精度算出准确结果】 【分解质因数 高精度乘法 --只用一次高精度提高运行效率】
较难 题目描述 输入a,b求C(a,b)的值。注意结果可能很大需要使用高精度计算。 【a b】 输入格式 共一行包含两个整数a和b。 输出格式 共一行输出C(a,b)的值。 数据范围 1≤b≤a≤5000 输入样例 5 3 输出样例 10 *公式C(a,b) a! / ( b! (a - b)! ) 【a b】 一般的处理方式先把C(a,b)分解质因数变成只有乘法的形式 --只要高精度乘法 -优化运算速度 质因子p个数运算 分母里面的有多少个p - 分子里的多少个p 差值就是个数 阶乘当中包含p的个数 a! 向下取整a/p1 [p1为p的倍数] 向下取整a/p2 [p2为p2的倍数] 向下取整a/p3 … 质数的次数【p的各种倍数中拿出一个p 得出所有含有p的项中p的总个数】【如p的k次方被加k次不重复不漏算 】 #includevector
const int N 5010;int primes[N],cnt;
bool st[N];
int sum[N];void get_primes(int n) //线性筛法
{for(int i 2;i n;i){if(!st[i]) primes[cnt ] i;//没有标记需遍历i的质数的倍数 筛除 [第一次i为2是质数先放入后面3,5同理4就被筛掉了]for(int j 0 ;primes[j] n / i;j) //遍历到 i sqrt(n) {st[primes[j] * i] true; //筛除i的质数的倍数 if(i % primes[j] 0) break; // i是pj 的倍数时后面已经筛选完了都是倍数就不用继续了结束 }}
}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)//t 0结束 {c.push_back( t % 10);t / 10; } return c;
}int main()
{int a,b;cin a b;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]); // (res 1) * primes[i] 的^sum[i]^次方 for(int i res.size() - 1;i 0;i --) printf(%d, res[i]);//vector遍历输出puts();return 0;
} 889.满足条件的01序列 【卡特兰数-用法极多】 题目描述 给定n个0和n个1它们将按照某种顺序排成长度为2n的序列求它们能排列成的所有序列中 能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。输出的答案对10^97取模。 输出格式 共一行包含整数n。 输出格式 共一行包含一个整数表示答案。 数据范围 1≤n≤105 输入样例 3 输出样例 5 思路 路径转换成一个排列 如坐标从0,0开始走0向右走1向上走到终点得到一个序列 当要求能走的坐标满足x y 时ans 即所有不经过y x 1这条边的数 所有走法 - 经过y x 1这条边的数 如(0,0)- - (6,6) 必走12步且选6步向上走 y x 1等效即C(12,6) - C(12,5) 扩展推 (0,0) 到 (n,n) 且不经过y x 1 即 Cat(n) C(nn , n) - C(nn , n-1) C(2*n,n) / (n 1) 【卡特兰数】 【卡特兰数应用栈的合法序列括号匹配数量… 简记 qmi(x的逆元) 在%p条件下可以表示为 1 / x
main :
①②求C(2n,n) ①先求 a! / (a-b)! for(int i a;i a - b;i --) res (LL)res * i % mod; //a! / (a-b)!②再求 1 / b! for(int i 1;i b;i ) res (LL)res * qmi(i,mod - 2,mod) % mod; ③最后再乘 1 / (n1) 【用 n1 的逆元表示】res (LL)res * qmi(n 1,mod - 2,mod) % mod;#includebits/stdc.h
using namespace std;typedef long long LL;
const int mod 1e9 7;//取模为质数
//因为%p所以都可以int
ll qmi(int a,int k,int p) //如果p不是质数那么逆元只能用扩展欧几里得定理求
{int res 1;while(k){if(k % 2) res (LL)res * a % p;a (LL)a * a % p;k 1; }return res;
}int main()
{int n;cin n;int a 2 * n , b n; int res 1;//求C(2*n,n) a! / b!(a-b)! 【C(a,a-b) * b!逆元分母】for(int i a;i a - b;i --) res (LL)res * i % mod; //a! / (a-b)!for(int i 1;i b;i ) res (LL)res * qmi(i,mod - 2,mod) % mod; //C(2*n,n) / (n1)res (LL)res * qmi(n 1,mod - 2,mod) % mod; // 乘(n1) 逆元 1/(n1) % pcout res endl;return 0;
}一篇不同代码的卡特兰数01序列
【其他代码-dp法参考】
卡特兰数 Cat(n)C2nn(n1)Cat(n) \frac{C_{2n}^n}{(n 1)}Cat(n)(n1)C2nn
带入试试是否满足样例 卡特兰数的简单代码实现 【DP】 组合数dp法求卡特兰数 c[a][b]仅能求 1 a,b 2000 Cat(n)C2nn−C2nn−1C2nnn1Cat(n) {C_{2n}^n} - {C_{2n}^{n-1}} \dfrac{C_{2n}^n}{n1} Cat(n)C2nn−C2nn−1n1C2nn
const int N 1e410;
int c[N][N]; //存组合数 c[a][b] 表示从a个苹果中选b个的方案数 【a b】void init() //init数组组合数
{
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; //逆推取第b个时是最后一个还是前面的最后一个取/不取 }int main()
{cin n;cout c[2*n][n] / (n1) ;return 0;
}分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV 当我们需要求出组合数的真实值而非对某个数的余数时分解质因数的方式比较好用 1. 筛法求出范围内的所有质数 2. 通过 C(a, b) a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p n / p^2 n / p^3 … 3. 用高精度乘法将所有质因子相乘
