组合数学
【组合数学】不定方程解个数问题 ( 多重集r组合数 | 不定方程非负整数解个数 | 生成函数展开式中 r 次幂系数 | 给定范围/系数 情况下不定方程整数解个数 )
文章目录多重集 r 组合数 生成函数计算方法多重集 r 组合数题目不定方程解个数 x 取值范围为 ( 0 ~ n )不定方程解个数 x 取值范围为 自然数 ( 0 ~ ∞ ) 符合多重集组合公式计算情况不定方程解个数 x 取值范围 ( 给定一个范围 )不定方程解个数 x 取值范围 ( 给定一个范围 并带系数 )不定方程解的题目 带限制的情况多重集 r 组合数 生成函数计算方法 此处引入 不定方程的
日期 2023-06-12 10:48:40
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
一. 生成函数 ( 母函数 ) 的定义1. 生成函数定义( 1 ) 生成函数的定义生成函数定义 :1.假设条件 : 设 是一个数列 ;2.形式幂级数 : 使用 该 数列 做 形式幂级数3.生成函数 :称上述是数列的生成函数;( 2 ) 形式幂级数 ( 参考 )形式幂级数 :1.幂级数 : 数学分析 中 重要概念 , 在 指数级的 每一项 均为 与 级数项 序号 相对应的 以 常数倍的的 次方 (
日期 2023-06-12 10:48:40
【组合数学】组合数学简介 ( 组合思想 3 : 上下界逼近 | 上下界逼近示例 Remsey 数 )
文章目录一、组合思想 3 : 上下界逼近二、上下界逼近示例 ( Remsey 数 )一、组合思想 3 : 上下界逼近上下界逼近 的思想 , 通常用于 确定某个值 , 或 确定某个函数的阶 ( 函数的量级 ) ;上下界逼近 步骤 :( 1 ) 证明值的上界( 2 ) 证明值的下界( 3 ) 如果 上界与下界值相等 , 则 证明结束( 4 ) 如果 上界与下界值不相等 , 则 改进上界 或 下界 ,
日期 2023-06-12 10:48:40【组合数学】鸽巢原理 ( 鸽巢原理简单形式 | 鸽巢原理简单形式示例 1、2、3 )
文章目录一、鸽巢原理简单形式二、鸽巢原理简单形式示例 1三、鸽巢原理简单形式示例 2四、鸽巢原理简单形式示例 3一、鸽巢原理简单形式鸽巢原理 :将 n + 1 个物体 放到 n 个盒子 中 , 则一定存在一个盒子 中 至少 含有 2 个 或 2 个以上的物体 ;鸽巢原理 实际上是 多对少的配置 ; 至少存在一个多对一的情况 ;二、鸽巢原理简单形式示例 1证明 : 在边长为 2 的正三角形中 ,
日期 2023-06-12 10:48:40
【组合数学】排列组合 ( 排列组合示例 )
文章目录一、排列组合示例 1 ( 组合 | 乘法法则 | 加法法则 )二、排列组合示例 2参考博客 :【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )一、排列组合示例 1 ( 组合 | 乘法法则 | 加法法则 )基本计
日期 2023-06-12 10:48:40【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 )
文章目录一、二项式定理二、组合恒等式 ( 递推式 1 )三、组合恒等式 ( 递推式 2 )四、组合恒等式 ( 递推式 3 ) 帕斯卡 / 杨辉三角公式五、组合分析方法六、递推式组合恒等式特点一、二项式定理二项式定理 :n 是正整数 , 对于一切 x 和 y , 有以下定理 :(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}\dbinom{n}{k}
日期 2023-06-12 10:48:40【组合数学】非降路径问题 ( 非降路径问题概要说明 | 非降路径问题基本模型 | 非降路径问题拓展模型 1 非原点起点 | 非降路径问题拓展模型 2 有途经点 )
文章目录一、非降路径问题 概要说明二、非降路径问题 基本模型二、非降路径问题 拓展模型 1三、非降路径问题 拓展模型 2组合恒等式参考博客 :【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 )【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和
日期 2023-06-12 10:48:40
【组合数学】递推方程 ( 递推方程示例 1 | 列出递推方程 )
文章目录一、递推方程示例 1二、递推方程示例小结一、递推方程示例 1编码系统使用 8 进制数字 , 对信息编码 , 8 进制数字只能取值 0,1,2,3,4,5,6,7 ,只有当某个编码含有 偶数个 7 时 , 该编码才是有效的 ,求 n 位的编码中有效的编码个数 ?分析 :n 位长的编码 , 可以 由 n-1 位长的编码 , 后面加上 一位 8 进制数字 构成 ;对于每个 n-1 位长的编码 ,
日期 2023-06-12 10:48:40
【组合数学】递推方程 ( 递推方程示例 2 汉诺塔 | 递推方程示例 3 插入排序 )
文章目录一、递推方程示例 2 汉诺塔二、递推方程示例 3 插入排序一、递推方程示例 2 汉诺塔Hanoi 问题 :递推方程为 : T(n) =2 T(n-1) + 1初值 : T(1) = 1解 : T(n) = 2^n - 1该递推方程表示 , 将 n 个盘子的移动次数 T(n) , 与 n-1 个盘子的移动次数 T(n-1) 之间的关系 ;解法参考 : 【组合数学】递推方程 ( 特特解示例 )
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 常系数线性齐次递推方程 | 常系数、线性、齐次 概念说明 | 常系数线性齐次递推方程公式解法 | 特征根 | 通解 | 特解 )
文章目录一、常系数线性齐次递推方程二、常系数、线性、齐次 概念说明三、常系数线性齐次递推方程公式解法四、常系数线性齐次递推方程公式解法内容概要一、常系数线性齐次递推方程常系数线性齐次递推方程 :\begin{cases} H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0 \\\\ H(0) = b_0 , H(1) = b_1 , H(2)
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 通解定义 | 无重根下递推方程通解结构定理 )
文章目录一、通解定义二、无重根下递推方程通解结构定理一、通解定义递推方程解的形式 : 满足 H(n) - a_1H(n-1) - a_2H(n-2) - \cdots - a_kH(n-k) = 0 公式的所有递推方程 , 都具有 c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n 形式的解 ;下面开始讨论之前得到的 解的形式 c_1q_1^n + c_2q_2^n +
日期 2023-06-12 10:48:40【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
文章目录一、生成函数性质总结二、生成函数与序列的对应参考博客 :【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 | 积
日期 2023-06-12 10:48:40【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
文章目录一、使用生成函数求解不定方程解个数1、带限制条件2、带系数参考博客 :【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求
日期 2023-06-12 10:48:40【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
文章目录一、正整数拆分基本模型二、有限制条件的无序拆分参考博客 :【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 |
日期 2023-06-12 10:48:40【组合数学】指数生成函数 ( 指数生成函数求解多重集排列示例 2 )
文章目录一、指数生成函数求解多重集排列示例 2参考博客 : 按照顺序看【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质
日期 2023-06-12 10:48:40组合数学之Polya计数 TOJ1116 Let it Bead
1116: Let it Bead Time Limit(Common/Java):1000MS/10000MS Memory Limit:65536KByteTotal Submit: 7 Accepted:4 Description "Let it Bead" com
日期 2023-06-12 10:48:40【BZOJ4555】求和（第二类斯特林数，组合数学，NTT）
【BZOJ4555】求和（第二类斯特林数，组合数学，NTT） 题面 BZOJ 题解 推推柿子 \[\sum_{i=0}^n\sum_{j=0}^iS(i,j)·j!·2^j \]\[=\sum_{i=0}^n\sum_{j=0}^nS(i,j)·j!·2^j \]\[=\sum_{i=0}^n\sum_{j=0}^nj!·2^j(\frac{1}{j!}\sum_{k=0}^j(-1)^k·C_
日期 2023-06-12 10:48:40【BZOJ4403】序列统计（组合数学，卢卡斯定理）
【BZOJ4403】序列统计（组合数学，卢卡斯定理） 题面 Description 给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。 Input 输入第一行包含一个整数T，表示数据组数。 第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。 1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R
日期 2023-06-12 10:48:40HDU 6397 Character Encoding (组合数学 + 容斥)
题意： 析：首先很容易可以看出来使用FFT是能够做的，但是时间上一定会TLE的，可以使用公式化简，最后能够化简到最简单的模式。 其实考虑使用组合数学，如果这个 xi 没有限制，那么就是求 x1 + x2 + x3 +... xm = k，有多少非零解，隔板法很容易得到答案 C(k+m-1, m-1)，但是有限制怎么办，使用容斥，考虑有一个变量超过 n-1，两个变量超过 n-1，等等，根据集合论，
日期 2023-06-12 10:48:40UVa 11645 Bits (暴力+组合数学)
题意：给定一个数 n，求 0 ~ n，中二进制表示中连续两个 1 出现的次数。 析：枚举连续的两个 1，从低位向高位进行枚举，然后前可以是任意数，后面也是任意的，如果 n 正好是 11 还要另算，举个例子。 10110，假设现在枚举第 2 位和第 3 位，那么出现的次次数就是前面的 10，还有第一位是任意的，所以就有 10 = 2 * 2 = 4 种，而且正好第 2 位和第 3 位是 1，那么对
日期 2023-06-12 10:48:40HDU 5321 Beautiful Set (莫比乌斯反演 + 逆元 + 组合数学)
题意：给定一个 n 个数的集合，然后让你求两个值， 1。是将这个集合的数进行全排列后的每个区间的gcd之和。 2。是求这个集合的所有的子集的gcd乘以子集大小的和。 析：对于先求出len，len[i]表示能够整除 i 的的个数。 第一个值，根据排列组合，求出gcd是 i 的倍数的个数， 解释一下这个式子，先从len[i]中选出 j 个数，然后进行排列，这就是所选的区间，然后再把这 j 个数看成一
日期 2023-06-12 10:48:40BZOJ 1005 [HNOI2008]明明的烦恼 (Prufer编码 + 组合数学 + 高精度)
1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5786 Solved: 2263[Submit][Status][Discuss] Description 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出
日期 2023-06-12 10:48:40CCF 201312-4有趣的数 (数位DP, 状压DP, 组合数学+暴力枚举, 推公式, 矩阵快速幂)
问题描述 我们把一个数称为有趣的，当且仅当： 1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。 2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。 3. 最高位数字不为0。 因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。 请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只
日期 2023-06-12 10:48:40组合数学第一发 hdu 2451 Simple Addition Expression
hdu 2451 Simple Addition Expression Problem Description A luxury yacht with 100 passengers on board is sailing on the sea in the twilight. The yacht is ablaze with lights and there comes out laugher
日期 2023-06-12 10:48:40【bzoj5004】开锁魔法II 组合数学+概率dp
题目描述 有 $n$ 个箱子，每个箱子里有且仅有一把钥匙，每个箱子有且仅有一把钥匙可以将其打开。现在随机打开 $m$ 个箱子，求能够将所有箱子打开的概率。 题解 组合数学+概率dp 题目约定了每个点的入度和出度均为1，因此最终的图一定是若干个环。每个环都至少选择一个点即可满足要求。 预处理出每个环的点数 $c[i]$ 以及其后缀和 $sum[i]$ 。 设 $f[i][j]$ 表示前 $i$
日期 2023-06-12 10:48:40