组合数学

\[X = \sum_{s=0}^{\min(n - m, k)} {n - m \choose s}^2 (s!) \sum_{x+y=k-s} {m \choose x}{n - m - s \choose x}{m \choose y}{n - m - s \choose y}(x!)(y!) ......

组合数学 概念 二项式定理 \[\begin{array}{l} (x+y)^{n} = \left(\begin{array}{cc} n \\ 0 \end{array} \right) x^{n}y^{0} + \left(\begin{array}{cc} n \\ 1 \end{array ......

P3799 妖梦拼木棒 又是一道要靠题解的思路的题。（难受）。 解题思路 首先，由于数据大小在5*1e3以内，数据量在1e5以内。所以用桶排记录无疑是最合适的。（记录下数据的最大值和最小值可以提高运行效率） 由题目分析，4个木棒中分三份（每份不为0）必然为1，1，2. 其次，我们用循环i遍历数组b[ ......

首先别犯一些脑残的定义错误：\(\binom{n}{m}=C_n^m\) 对称恒等式：\(\binom{n}{m}=\binom{n}{n-m}\) 吸收恒等式：\(m\binom{n}{m}=n\binom{n-1}{m-1}\) \(\text{Catalan}\) 数列 \[H_n = \df ......

初赛题目中往往会出现将多少东西（相同或者不同），分到一些容器（相同或者不同）中，允许或者不允许空的问题，这里我们就统一总结一下。 本篇博客中，物品统一称为苹果，容器统一称为盘子，因而得名为苹果盘子问题。 1.苹果相同，盘子不同，不允许空 思路：既然苹果是相同的，盘子是不同的，那么实际上我们的问题就是 ......

排列组合 \[A_m^n=\frac{n!}{(n-m)!} \]\[C_{m}^{n}=\frac{n!}{m!(n-m)!} \]\[C^n_0+C_1^n+C_2^n+...+C_n^n=2^n \]\[C_m^n+C_m^{n+1}=C_{m+1}^{n+1} \]\[C_m^n=C^n_{ ......

组合数学 排列组合——插板法： 例1：\(n\) 个相同的球，放入 \(m\) 个不同的盒子且不能有空盒存在，方案数是多少？ 我们考虑使用插板法，一共 \(n\) 个球，\(n-1\) 个间隔，选出 \(m-1\) 个间隔，就可以将 \(n\) 个球分成 \(m\) 组，方案数 \(\binom{n ......

题目链接🔗 分析一下题意：给定一个初始数组A，以及m次操作，每一次操作会改变一个A中的数字，一共得到m+1个数组。 现在，要求出任意两个数组两两组合的情况中：所有的不重复数字出现次数的总和。 这道题想了很久，乍一看以为是模拟，手画递归找规律一直没想出来。看了题解思路，发现出发点就错了：因为每个数组 ......

组合数学 球盒模型: https://zhuanlan.zhihu.com/p/429815465?utm_id=0 简单 进阶 集美大学2023新生赛 C. 方格染色 ......

组合数学与组合计数 计数原理 分类加法计数原理：做一件事，有多类方法，则总的方法数是所有类方法数之和。 分步乘法计数原理：做一件事，需要多步完成，则总的方法数是所有步方法的乘积。 例题：P3197 [HNOI2008] 越狱 排列与组合 排列数：从 \(n\) 个数中选出 \(m\) 个数排成一列， ......

CF1764D Doremy's Pegging Game 你怎么连简单题也不会？ 考虑满足条件当且仅当有连续的n/2向下取整段被删除。 考虑最终状态一定是一次删除联通了两个连续段，然后结束。 我们枚举这个连续段的长度 i 。 最后一个删除的位置有 n/2下取整*2-i 种方案，设另外删除了 j 种 ......

组合数学 二项式定理 ​ $ (a + b)^n = \sum \limits_{i = 0}^{n} \dbinom {n} {i} a^i b^{n - i} $ ​ 证明 ： 考虑组合意义，对于一项 \(a^i b^{n - i}\) ，需要在 \(n\) 个 \((a + b)\) 中选出 ......

题目：从前有一只青蛙他想跳台阶，有n级台阶，青蛙一次可以跳1级台阶，也可以跳2级台阶；问：该青蛙跳到第n级台阶一共有多少种跳法。 当只有跳一级台阶的方法跳时，总共跳n步，共有1次跳法 当用了一次跳二级台阶的方法跳时，总共跳n-1步，共有n-1次跳法 当用了两次跳二级台阶的方法跳时，总共跳n-2步，共 ......

组合数学与计数复习 前言： 自从发现，每次打 codeforces 或者模拟赛，看到“方案数mod 998244353”就直接跳过了， 这一次为了突破此类题，所以专门对其进行复习。 题单：（洛谷） 链接 硬核知识： 加法原理和乘法原理 感觉就是同类的是加和，互不影响的是乘法。 这个东西常常应用在dp ......

排列组合 OI-wiki Link 排列组合是组合数学的基础，排列就是取出部分数字进行排序，组合就是不考虑顺序。 排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 加法、乘法原理 加法原理：一个东西有 \(n\) 类办法，第 \(i\) 类办法分 \(a_i\) 种，总共就有 \(\ ......

模板 （前置芝士） P1226 【模板】快速幂 | 取余运算 目的： 顾名思义，快速求解乘方。 实现： 挺好写的。 题目传送门 代码 P3811 【模板】乘法逆元 开long long!! 定义： 若 \(a * x\equiv1\pmod b\) ，且 \(a\) 与 \(b\) 互质，那么就能定 ......

这是一位数学小萌新看 oi-wiki 的一点点收获。 二项式定理 二项式定理是组合数学中很基础且很重要的定理，它的式子为： \((a+b)^n= \sum_{i=0}^n \binom{n}{i} a^i b^{n-i}\) 可以通过归纳法剖析 \((a+b)^n\) 的过程证明其正确性。 范德蒙德 ......

排列 从n个不同元素中取出m（m≤n）个元素的所有的排列情况。用表示 公式为： 示例A：从1，2，3，4这几个数字中，取2个数字组成2位数，有多少种情况。 组合 从n个不同元素中取出m（m≤n）个元素的所有的情况。用表示 公式为： 与排列的区别：取出的元素顺序如何没有影响。比如：示例A中，先取出1再 ......

常用积性函数： \(\bullet\) 单位函数 \(\varepsilon(n)\text{ = }\begin{cases}\text{1, while n=1}\\\text{0, otherwise}\end{cases}\) \(\bullet\) 幂函数 \(\begin{cases}I ......

# 组合数学第五章练习题（部分） ## 11. $$ \binom{n}{k} - \binom{n - 3}{k} = \binom{n - 1}{k - 1} + \binom{n - 2}{k - 1} + \binom{n - 3}{k - 1} $$ 理树要在神北私立高级中学的 $n$ 位 ......

## 一、加乘原理 ### 加法原理 一件事，有 $n$ 类方法可以实现它，第 $i$ 类方法有 $a[i]$ 种方法实现，那么总共有 $\sum_{i=1}^na[i]$ 种方法实现。 ### 乘法原理 一件事，有 $n$ 个步骤可以实现它，第 $i$ 个步骤有 $a[i]$ 种方法实现，那么总共 ......

## 组合数学练习复习 个人感觉：不看题解没思路，看了题解不知所云，亲自推柿子wa上加wa,平均1道题看题解要做1.5h…… ### 排列组合 1. 首先，你需要会打线性筛逆元（基础）。 代码如下： ```c++ void init(int N){ inv[1]=1; fac[0]=1; invfa ......

# Problem 1 **题意**：从 $S=\{1,2,\dots,200\}$ 中选出一个集合 $T$，其中 $|T| = 100$ 且 $\displaystyle \min_{i=1}^{100}T_i < 16$，证明对于任意的 $T$ 都存在 $i,j$ 满足 $1 \leq i,j ......

# 1. 容斥原理 ## 1.1 介绍 解决集合内计数问题。 $S$ 为集合编号集合。 $$\left | \bigcup_{i\in S}A_i \right | =\sum_{T\subseteq S\wedge T\ne \varnothing}^{n}(-1)^{(\left | T \ri ......

## 1.[分特产](https://www.luogu.com.cn/problem/P5505)： 首先考虑分设 $f_i$ 与 $g_i$ 分别表示钦定与恰好，由题意我们容易知道 $f_i$ 首先应钦定 $i$ 个人，方案为 $\binom{n}{i}$，然后对剩下的 $n-i$ 个人插 $a ......

## 参考资料 [OI-Wiki 组合数学](https://oi-wiki.org/math/combinatorics/combination/) ## 一、 概念 $\dbinom{n}{m}$ 表示从 $n$ 个小球内拿 $m$ 个的方案数，小球一样但顺序不一样算同一种方案，可用 $\dbi ......

#### 排列组合 从 $n$ 个互不相同的球里选出 $m$ 个，顺序有影响则称为排列，没有影响则称为组合。 $P_n^m$ 表示排列的方案数，$C_n^m$ 表示组合的方案数。其中 $C_{n}^m$ 也可表示为 $\binom nm$，$P_n^m$ 在数值上与 $n^{\underline m ......

# 前置芝士 ## 加法原理 完成一项工作有 $n$ 类方法，每类方法有 $a_i$ 种，则总共有 $\sum\limits_{i=1}\limits^{n} a_i$ 种方法完成这项工作。 ## 乘法原理 完成一项工作有 $n$ 个步骤，每个步骤有 $a_i$ 种方法，则 $\prod\limit ......

上文：[组合数学初步](https://www.cnblogs.com/wangwenhan/p/17589679.html "组合数学初步") # Stirling 简述 ## Stirling formula ![image](https://img2023.cnblogs.com/blog/3 ......

# 入门： 先介绍三个简单的技术 ## 插板法： ### 直接插板： 看下面的问题： #### eg1: $x+y+z=20$，其中$x,y,z$为正整数，求有多少组解。 我们考虑有$20$个球排成一排。我们插入两个板子把这$20$个球分成$3$个部分，其中第一部分的球的个数是$x$的大小，第二部分 ......