组合计数
关于记号
\[C_n^m={n\choose m}=A_n^m/m!=n^{\underline{m}}/m! \]插板法
-
插板法：分集合问题 \(\iff\) 不定方程正整数解计数问题
\[{n-1\choose m-1} \]创造条件法（构造双射），即，构造元素集合 \(A,B\)，以及一个 \(A,B\) 之间的双射 \(f\)，则把计数 \(A\) 变成计数 \(B\) 。
如果允许集合为空，则问题可以转化为添加 m 个球时不允许为空的问题
-
不定方程解计数：有上界。难以处理，可以采用容斥。枚举几个大于限制，则能够求出至少 \(i\) 个大于 \(k\) 。
基本容斥思想：总共减去不符合的等于答案==交集等于全集减补集并集
\[\begin{aligned} \]
&+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}{m}S_{a_i}\right|+\cdots+(-1)|S_1\cap\cdots\cap S_n|
\end{aligned}
H_n = \binom{2n}{n} - \binom{2n}{n-1}
\[ 本方法叫做 **折线容斥**  - [JLOI2015] 骗我呢：性质1：每行都有恰好一个 [0,m] 中没有出现  式子的系数很简单，则可以 **在网格图上画出转移**，可转化为不碰到两条直线的路径数。 ## Stirling 类似 dp 思路 - 第一类 Stirling 数：求把 $n$ 个不同元素构成 $m$ 个非空圆排列的方案数。 第二类 Stirling 数 ：求把 n 个不同元素划分 m 个非空子集的方案数 \]\def\stira#1#2{\begin{bmatrix}#1\ #2\end{bmatrix}}
\def\stirb#1#2{\begin{Bmatrix}#1\ #2\end{Bmatrix}}
\stira{n}{k}=\stira{n-1}{k-1}+(n-1)\stira{n-1}{k}\
\stirb{n}{k}=\stirb{n-1}{k-1}+k\stirb{n-1}{k}
\def\stira#1#2{\begin{bmatrix}#1\ #2\end{bmatrix}}
\def\stirb#1#2{\begin{Bmatrix}#1\ #2\end{Bmatrix}}
mn=\sum_{i=0}m{\stirb{n}{i}m^{\underline{i}}}
\sum_{i=0}^n{i\choose k}={n+1\choose k+1}
\[ 证明1 该问题可以与 $n+1$ 个元素的 $k+1$ 大小子集个数建立双射，原因如下： \]{n+1\choose k+1}=\sum_{i=1}^{n+1} { i-1\choose k}=\sum_{i=0}^{n} { i\choose k}
\[ 以上求和的意义是枚举其中一个元素的位置。 证明2 当然上述公式求和的下标还可以改为 $i=k$ ，此时补充一个 ${k\choose k+1}$ (?) 证明3 按照递推公式依次展开可以得到。 - 自然数幂和-拉格朗日插值 $n+1$ 个点值可以唯一确定一个 $n$ 次多项式。使用： \]f(x) = \sum_{i=1}^{n} \prod_{j\neq i }\frac{x-x_j}{x_i-x_j} y_i
\[ 将点值带入易证  ## 其他模型 - AGC013D：转化问题是比较容易的。重复处理：对于所有平移可以产生的重复方案，我们强制其“贴边界”（即曾经到底过0）才记录答案，考虑设  - CF1895F：关键转化：**弱化限制/差分法**  正确性显然。 条件2让我们想到差分数组，该条件可以转化为差分数组取值在 $[-k,k]$ 之内 现在还需要表达最小值的限制，我们可枚举最小值的限制，配合计算差分数组的数量，可以知道这一部分答案是 $(x+k)(2k+1)^{n-1}$ 对于最大值那一部分的答案，考虑 $x$ 很小，设 $f_{i,j}$ 表示填了 $i$ 个数，最后一个是 $j$ ，可以矩阵快速幂计算。 \] 标签：lg,组合,计数,sum,2950259,括号,choose,stirb From： https://www.cnblogs.com/haozexu/p/18350552