《组合数学》
XDOJ1145–组合数学四之Carnival Phantasm
大家好，又见面了，我是你们的朋友全栈君。描述：为解救可怜的武内崇老师，saber、远坂、爱尔奎特、希耶尔等人组成了第六科急救队！最终，由琥珀开发出了禁药，分身光线（这药是内服还是外用的= =？）,将爱尔奎特批量化生产，来对月世界进行全面的地毯式搜索。现已知，第六科共有m个复制人（每个复制人完全一样），月世界有n个城市，每个城市会被一个复制人搜索一遍。问：共有多少种分配方法。（根据时空管理局劳务法更
日期 2023-06-12 10:48:40
P2181 对角线 【排列组合 | 数学】
题目：https://www.luogu.com.cn/problem/P2181题意：给一个 n 边形，将所有对角线连起来，问一共有多少个交点。题解：看到一个蛮好的理解，两条线会有一个焦点，那么反映在 n 边形上，就是四个点就会有一个交点，所以问题就变成了任取四个点，有多少种取法？#include<stdio.h> #include<bits/stdc++.h> usin
日期 2023-06-12 10:48:40
【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
文章目录1. 加法原则( 1 ) 加法原则 ( 不能叠加 的事件才能用 加法原则 | 适用于 分类选取 )( 2 ) 乘法法则 ( 相互独立 的 事件 才能用 乘法法则 | 适用于 分步选择 )2. 习题解析( 1 ) 习题 1 ( 加法原理 )( 2 ) 习题 2 ( 加法原则 乘法原则 综合运用 )( 3 ) 习题 3 ( 乘法原则 )1. 加法原则( 1 ) 加法原则 ( 不能叠加 的事件才
日期 2023-06-12 10:48:40【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
文章目录一、集合排列 和 多重集排列问题 1二、 集合排列 和 多重集排列问题 2三、 找一一对应计算集合排列问题 ( 反向计算 )四、 圆排列问题 1五、 集合交替排列问题六、 圆排列问题 2七、 推广的牛顿二项式公式八、 二项式展开问题一、集合排列 和 多重集排列问题 1题目 :1.条件 : 由 字母 a, b,c,d,e,f 组成 4 个字母的单词 ;2.问题 1 : 每个字母在单词中 最多
日期 2023-06-12 10:48:40【组合数学 】 推广牛顿二项式 ( 牛顿二项式推广 | 推导流程 | 题目解析 )
文章目录牛顿二项式公式牛顿二项式公式 使用 ax 替换 x 后的公式推广牛顿二项式公式 二项式幂是负数的情况推导 C(-n,k) 的公式推广牛顿二项式题目解析1题目解析2牛顿二项式公式(1 + x)^n = \sum_{k=0}^{n} \dbinom{n}{k}x^k牛顿二项式公式 使用 ax 替换 x 后的公式公式推导 : 使用 ax 替换 x , 然后将公式展开即可 : \begin{ar
日期 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【组合数学】排列组合 ( 集合组合、一一对应模型分析示例 )
文章目录一、集合组合、一一对应模型分析示例排列组合参考博客 :【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )【组合数学】排列组合 ( 排列组合示例 )【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集
日期 2023-06-12 10:48:40【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
文章目录一、组合恒等式 ( 递推式 )二、组合恒等式 ( 变下项求和 ) 简单和二、组合恒等式 ( 变下项求和 ) 交错和一、组合恒等式 ( 递推式 )组合恒等式 ( 递推式 ) :1 . \dbinom{n}{k} = \dbinom{n}{n-k} , 作用 : 化简2 . \dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} , 作用 : 求和
日期 2023-06-12 10:48:40
【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )
文章目录一、组合恒等式 ( 变下项求和 ) 变系数求和 1二、组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 + 求导 )三、组合恒等式 ( 变下项求和 ) 变系数求和 2四、组合恒等式 ( 变下项求和 ) 变系数求和 2 证明 ( 使用已知恒等式证明 )一、组合恒等式 ( 变下项求和 ) 变系数求和 1组合恒等式 ( 变下项求和 ) 变系数求和 :\sum_{k=0}^{n
日期 2023-06-12 10:48:40
【组合数学】递推方程 ( 递推方程内容概要 | 递推方程定义 | 递推方程示例说明 | 斐波那契数列 )
文章目录一、递推方程 内容概要二、递推方程 定义三、递推方程 示例四、斐波那契数列 ( Fibnacci )一、递推方程 内容概要递推方程 内容概要 :递推方程定义递推方程实例常系数线性递推方程 常系数线性递推方程定义公式解法递推方程在计数问题中的应用二、递推方程 定义序列 a_0 , a_1 , \cdots , a_n , \cdots , 记做 \{a_n\} ,将 a_n 与 某些 a_
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 无重根递推方程求解实例 | 无重根下递推方程求解完整过程 )
文章目录一、斐波那契数列求解二、无重根下递推方程求解完整过程一、斐波那契数列求解1 . 斐波那契数列示例 :( 1 ) 斐波那契数列 : 1 , 1 , 2 , 3 , 5 , 8 , 13 , \cdots( 2 ) 递推方程 : F(n) = F(n-1) + F(n-2)描述 : 第 n 项等于第 n-1 项 和 第 n-2 项之和 ;如 : 第 4 项的值 F(4) = 5 , 就等于第
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 有重根递推方程求解问题 | 问题提出 )
文章目录一、有重根递推方程求解问题二、有重根递推方程示例一、有重根递推方程求解问题有些 递推方程 的 特征方程 的 特征根 有 重根 的情况 , 特征方程解出来的 特征根有一部分是相等的 , 这样就使得 通解中的常数无法获取唯一的值 ;参考 : 【组合数学】递推方程 ( 通解定义 | 无重根下递推方程通解结构定理 ) 二、无重根下递推方程通解结构定理在 “无重根下递推方程通解结构定理” 章节中 ,
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 有重根下递推方程通解结构 | 线性无关解 | 有重根下的通解 | 有重根下的递推方程求解示例 | 递推方程公式解法总结 ) ★
文章目录一、线性无关解二、有重根下的通解二、有重根下的通解写法三、有重根下的递推方程求解示例四、递推方程公式解法总结一、线性无关解线性无关解 :如果 q 是递推方程的 e 重特征根 , 则q^n , nq^n , n^2q^n , \cdots , n^{e-1}q^n是递推方程的 线性无关的解 ;e 是特征根的重数 ;二、有重根下的通解q_1, q_2, \cdots , q_t 是递推方程的
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 特解形式 | 特解求法 | 特解示例 )
文章目录一、特解形式与求法二、特解形式与求法 示例一、特解形式与求法H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = f(n) , n\geq k , a_k\not= 0, f(n) \not= 0上述方程左侧 与 “常系数线性齐次递推方程” 是一样的 , 但是右侧不是 0 , 而是一个基于 n 的 函数 f(n) , 这种类型的递推方程称为 “常系数线性非齐次递推
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 非齐次部分是指数的情况 | 非齐次部分是指数的情况示例 )
文章目录一、非齐次部分是指数的情况二、非齐次部分是指数的情况 示例一、非齐次部分是指数的情况常系数线性非齐次递推方程 : H(n) - a_1H(n-1) - \cdots - a_kH(n-k) = f(n) , n\geq k , a_k\not= 0, f(n) \not= 0上述方程左侧 与 “常系数线性齐次递推方程” 是一样的 , 但是右侧不是 0 , 而是一个基于 n 的 函数 f(n
日期 2023-06-12 10:48:40【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
文章目录一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式二、递推方程通解的四种情况一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式如果 “常系数线性非齐次递推方程” 的非齐次部分 , 是 n 的 t 次多项式 , 与 \beta^n 的指数 , 的组合 ;那么其特解的形式 , 是 n 的 t 次多项式 , 与 P\beta^n 的 和 ;递推方程
日期 2023-06-12 10:48:40【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
文章目录一、生成函数性质总结二、生成函数与序列的对应参考博客 :【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 | 积
日期 2023-06-12 10:48:40【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
文章目录一、生成函数应用场景二、使用生成函数求解递推方程参考博客 :【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 |
日期 2023-06-12 10:48:40【组合数学】指数生成函数 ( 指数生成函数性质 | 指数生成函数求解多重集排列 )
文章目录一、指数生成函数性质二、指数生成函数求解多重集排列参考博客 : 按照顺序看【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 |
日期 2023-06-12 10:48:40【组合数学】指数生成函数 ( 指数生成函数求解多重集排列示例 )
文章目录一、指数生成函数求解多重集排列示例参考博客 : 按照顺序看【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 |
日期 2023-06-12 10:48:40POJ 3252 Round Numbers（组合数学）
Round Numbers Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 10223 Accepted: 3726 Description The cows, as you know, have no fingers or thu
日期 2023-06-12 10:48:40【BZOJ1485】[HNOI2009]有趣的数列（组合数学）
【BZOJ1485】[HNOI2009]有趣的数列（组合数学） 题面 BZOJ 洛谷 题解 从小往大填数，要么填在最小的奇数位置，要么填在最小的偶数位置。 偶数位置填的数的个数不能超过奇数位置填的数的个数。 好的，卡特兰数。 诶，woc，我不会卡特兰数啊。行，来学一下。 \(H(0)=H(1)=1\) \(H(n)=\sum_{i=0}^{n-1} H(i)H(n-i-1)\) \(H(n)=H
日期 2023-06-12 10:48:40【BZOJ2425】[HAOI2010]计数（组合数学）
【BZOJ2425】[HAOI2010]计数（组合数学） 题面 BZOJ 洛谷 题解 很容易的一道题目。 统计一下每个数位出现的次数，然后从前往后依次枚举每一位，表示前面都已经卡在了范围内，从这一位开始比目标小。 对于长度小于当前数的个数，我们可以默认它们有前导零就行了。 #include<iostream> #include<cstdio> #include<cs
日期 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【BZOJ1004】Cards（组合数学，Burnside引理）
【BZOJ1004】Cards（组合数学，Burnside引理） 题面 Description 小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有 多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方 案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,
日期 2023-06-12 10:48:40【BZOJ3997】[TJOI2015]组合数学 最长反链
【BZOJ3997】[TJOI2015]组合数学 Description 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。 Input 第一行为正整数T，代表数据组数。 每组数据第一行为正整数N，M代
日期 2023-06-12 10:48:40并查集+组合数学
A. Bear and Friendship Condition 并查集：每个集合的个数，如果集合若是有向强连通分量，则集合内边数必须满足n*(n-1)/2 #include &l
日期 2023-06-12 10:48:40HDU 4609 3-idiots (组合数学 + FFT)
题意：给定 n 条边，问随机选出 3 条边，能组成三角形的概率是多少。 析：答案很明显就是 能组成三角形的种数 / (C(n, 3))。现在的问题是怎么求能组成三角形的种数。 这个博客说的非常清楚了。。。 https://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html 总体来说就是把边长转换成下标，然后再根据组合数，就
日期 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:40