组合数学

# 康托展开 将 $1...n$ 的所有排列按照字典序进行排序，某个排列的排名可以通过康托展开的方法求出。 ## 原理 观察排列 $2,3,1,4$ 和 $2,3,4,1$，发现第一个不同的位置是第三位，而且第一个排列的第三位比第二个小，根据字典序的性质，第一个排列的排名在第二个之前。 从这里我们也 ......

# 组合数学相关 约定：无特殊说明，以下字母所代表的数均为非负整数。 ## 一些符合及其含义 * $n!:= 1 \times 2 \times 3 \times … \times n$，特别地， $0!=1$ * $ \binom{n}{m} = \frac{n!}{m!(n-m)!} $，表示 ......

# 组合数学学习笔记 ## 组合数学常用公式 ### 基本公式 1. 排列： $$ A_{n}^r=\frac{n!}{(n-r)!} $$ 2. 组合: $$ C_{n}^r=\frac{n!}{r!(n-r)!} \\ \dbinom{n}{r}=\frac{n!}{r!(n-r)!} $$ # ......

# 组合数学 笔寄 ## 加法原理 完成一个事情有 $n$ 类**做法**，第 $i$ 类做法又分为 $a_i$ 种。所以这件事情有 $S=\sum_{i=1}^{n}a_i$ 的不同的完成方法。 ## 乘法原理 草字头有 $3$ 种写法，回字有 $4$ 种写法，所以茴香豆的茴有 $S=3\time ......

# 组合数 **本文为转载的文章**，转载自：[组合 - hfjh](https://www.cnblogs.com/hfjh/p/17519646.html) 默认会组合数基础内容和[二项式定理](https://oi-wiki.org/math/combinatorics/combination ......

加法原理、乘法原理等是组合数学中的基础 加法原理 将集合S划分为S1,S2,S3,......,Sm,则|S|=|S1|+|S2|+|S3|+......+|Sm| 乘法原理 定义集合S是元素序列(a,b)的集合，对于元素a有P种选择，元素b有Q种选择，则S的大小为P*Q 排列 一.不可重复排列数 ......

title: 组合数学总结 date: 2023-06-07 07:22:17 tags: 总结 cover: https://i.imgloc.com/2023/06/07/Vl1VpL.jpeg 本篇文章是为了总结一下最近做的组合数学的题目以及涉及到的知识点，以后可能会不定期补充。同时也参考了大 ......

# 组合数学与计数 笔记，不含练习。 ## 基本计数原理 加法原理 乘法原理 ## 组合数 $\binom{n}{r}$ 或 $C_{n}^{r}$ 表示组合数，从 $n$ 个元素中选 $r$ 个的方案数，不考虑顺序。$\binom{n}{r}=C_n^r=\frac{n!}{r!(n-r)!}$。 ......

题目大意: 给一个树, 然后 有k 种颜色可以给树上色 权值是 2个相同颜色节点的最短距离 问 让权值为 D 的方案数 题解: 首先 要让2个节点为D, 怎么处理呢? 利用 f(D)- f(D+1) 即可 因为问的是 2个相同颜色点的最短距离, 因此直接bfs用一个bfs序列 然后在bfs一下, 因 ......

### 错位排列 ### 二项式定理 $${(a + b)^k} = \sum_{i=0}^k {k \choose i} * a ^ i * b^{k - i}$$ 似乎比较显然。接下来是关于二项式定理的几个推论。 #### 推论一 $${(a + b)^k} = \sum_{i=0}^k {k ......

## B. AquaMoon and Chess [Problem - 1545B - Codeforces](https://codeforces.com/problemset/problem/1545/B) 题意：给定一个1*n的方格，有些方格有棋子，每个棋子可以这样移动： 1，当i,i+1有棋 ......

#### 插板法 问题一：现有 $n$ 个 完全相同的元素，要求将其分为 $k$ 组a，保证每组至少有一个元素，一共有多少种分法？ 考虑拿 $k-1$ 块板子插入到 $n$ 个元素两两形成的 $n-1$ 个空里面。 所以答案就是 $$\binom{n-1}{k-1}$$ 问题二：如果问题变化一下，每 ......

本文部分内容来自 $\texttt{OI-Wiki}$。 **** ## 加法 & 乘法原理 加法原理 完成一个工程可以有 $n$ 类办法，$a_i(1 \le i \le n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S=a_1+a_2+\cdots +a_n$ 种不同的方法。 乘法 ......

（递推计算组合数）[P4071 [SDOI2016]排列计数](https://www.luogu.com.cn/problem/P4071 "P4071 [SDOI2016]排列计数") 吐个槽先：没啥好吐槽的, 就是我自己傻掉了. Orz. 这题的式子非常水. 1. 在 $n$ 个数里面选 $m ......

### 二分图匹配和霍尔定理 #### 相异代表系 我们用一个相异代表系描述二分图匹配问题。我们有若干个集合 $\{S_1,S_2,S_3,\cdots,S_m\}$，现在要给每个集合选定一个代表 $x_i\in S_i$，并且每个 $x_i$ 是相异的。 容易发现这个问题和二分图匹配问题是等价的。 ......

废话不多说，直接开始讲吧。 # 加法&乘法原理 略。 # 排列与组合基础 ## 排列数 组合数就是从 $n$ 个不同元素中选择 $m$ 个元素组成**列表**的方案数，记作 $A_n^m$ 。 计算排列数的公式为： $\displaystyle A_n^m=\frac{n!}{(n-m)!}$ 。 ......

1648：【例 1】「NOIP2011」计算系数 第一种方法：直接用杨辉三角求出二项式系数 #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const ......

> 题目链接：https://ac.nowcoder.com/acm/contest/58860 > > 来源：牛客网 ## 题目描述 > 统计树上所有的非空点集 $S$ 其最近公共祖先结点的权值 $a_{\mathrm{LCA}(S)}$ , 如果为 $|S|$ 为偶数则加，否则减。 > > $\ ......

###[原题点这](https://codeforces.com/contest/1832/problem/E) ###前置知识点： 组合数学 ###题意： 给你一个数组 a 和 k, 让你计算一个新的数组 b。 给你 $a_1$ , 对于$ 2 \le i \le n $, $ a_i = (a_ ......

# 排列组合 > 排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。 OI Wiki ### 乘法原理和加法原理 加法原理，就好比一个工作，有 $n$ 个解决的方案，第 $i$ 项方案有 $a_{i}$ 种不同的实现方式，所以这个 ......

自动取模型 template<int mod> struct ModZ{ LL x; ModZ(LL t = 0) {t %= mod; if (t < mod) t += mod; x = t;} ModZ power(ModZ a, LL b) {ModZ res = 1; for (; b; ......

设 $a$ 数组的前缀和为 $s_i$，$b$ 数组的前缀和为 $t_i$，那么根据模拟费用流或者贪心的思想，每一条边经过的次数即为 $|s_i-t_i|$，因此非常 trivial 的做法是转换贡献体，枚举每种方案下每条边被经过的次数，然后乘以 $w_i$ 求和，具体来说： $$ ans=\sum ......

阅读前须知 ​ 本博客包含了一些提高到省选难度的组合数学知识点，主要由知识点和笔者做题时遇到的一些题组成。 ​ 对于知识点，阅读前需要你掌握最基础的一些组合数学知识，如排列数组合数，插板法等等，还需要一定的推式子能力，其中还会涉及到一部分与多项式和生成函数有关的内容，读者可以自行选择阅读。同时由于笔 ......

题目： 在一个平面内有n(n>=3)个不完全共线的点，求证：则该平面内至少存在一条线恰好穿过其中两点 证明： 考查这个平面上每个至少经过两点的边以及对于一条边，不在该边上的点到边的最短长度。 考虑上面最短长度中最短的一条边和一个点 则该边恰好经过两个点 证明如下： 如上图所示，假如直线AB与C是最短 ......

题目： 任意mn+1个不同的数排成一列，求证：要么存在m+1项递增数列，要么存在n+1项递减数列 一、分析 为什么要任意mn+1个数呢？是不是说明mn个数存在不满足的情况？我们可以先尝试寻找mn个数的情况 我们发现： n,n-1,...,1, 2n,2n-1,...,n-1, ......, mn, ......

加法原理 完成一件事，有 $m$ 类方法，对于每类方法有 $s_i$ 个方案，则此时总方案数就是 $\sum_{i=1}^m s_i$。 乘法原理 完成一件事，有 $n$ 个步骤，对于每个步骤有 $s_i$ 个方案，则此时总方案数就是 $\prod_{i=1}^n s_i$。 排列 从 $n$ 个数 ......

题目链接：https://ac.nowcoder.com/acm/contest/54484/B 题意很简单，但是数据范围偏大。 错排公式 首先来推导一下错排公式： $$D(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$ 设一个函数： $$S_i表示一个排列中p_i ......

引例1、（姐妹洗碗问题） 思考过程： 横坐标表示姐姐洗完的碗的个数，纵坐标表示妹妹摞碗的个数，前提条件为妹妹摞碗的个数不能超过姐姐洗完的碗的个数，要求摞法的方案数实际上是求从坐标（0，0）到坐标（5，5）的所有满足条件的路径数。 引例2、（进出栈问题） 思考过程： 本质上和姐妹洗碗问题一致，都是求方 ......

题目链接：https://codeforces.com/contest/1809/problem/G 题解： 一道很强的 dp 首先翻译条件：predictable 是什么意思？发现就是对每一个下标，前缀 max 和下一个位置至少差一个 $k+1$ 看到 $n \leq 10^6$，可以猜测最后应该 ......

DAY4共2题： 树（组合数学） 子序列（dp，数学） 🎈 作者：Eriktse 🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀 🎈 原文链接（阅读原文获得更好阅读体验）： ......