杨辉三角 void init() { for (int i = 0; i < N; i++) { c[i][0] = 1; c[i][i] = 1; for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P; } } 线性推阶乘与阶乘逆元 int …

二项式定理 普通二项式定理： $$ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i $$ $$ \begin{pmatrix}m\cr 0\end{pmatrix}+\begin{pmatrix}m\cr 1\end{pmatrix}+\cdots+\begin{pmatrix}m\cr m\end{pmatr…

错位排列 对于 $1\sim n$ 的排列 $P$ 如果满足 $P_i\neq i$ ，则称 $P$ 是 $n$ 的错位排列。求 $n$ 的错位排列数。 递推式： 假设前 $n-1$ 个已经放好，第 $P_n$ 位置放了 $n$。如果前 $n-1$ 个已经是错位排序，则将 $P_n$ 与前面任意一个交换，可以产生一个 $n$ 的错位排序；如果前面只…

公式 定义： $$ h(n)=\sum_{i=0}^{n-1}h(i)b(n-1-i) $$ 生成函数： $$ F(x)=xF^{2}(x)+1=\frac{1-\sqrt{1-4x}}{2x} $$ 性质： $$ \begin{aligned} h(n)&=\frac{\binom{2n}{n}}{n+1}\cr h(n)&=C_…

第一类斯特林数 性质与结论 $\left[\begin{matrix} n \cr m \end{matrix}\right]$ 表示 $n$ 个不同的元素构成 $m$ 个圆排列的数目。 递推式：最后一个元素成单独一个圆排列，有$\left[\begin{matrix}n-1 \cr m-1 \end{matrix}\right]$种方案；若前$n…

定义：定义贝尔数 $B_n$ 为：$n$ 个元素划分为任意个集合的方案数。由第二类斯特林数定义可得： $$B_n=\sum_{i=0}^{n}\begin{Bmatrix}n\cr i\end{Bmatrix}$$ 递推式： $$B_{n+1}=\sum_{i=0}^{n}\binom{n}{i}B_i$$ 由此可以 $O(n^2)$ 递推； To…

题目链接：hdu4651 Partition 动规做法 设 $f[n][m]$ 为 $n$ 个球放到 $m$ 个盒子里的方案数。则 $n$ 的整数拆分方案等于 $f[n][n]$。 如果只有一个盘子或者没有小球，方案数自然为 $1$ 如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移 $f[i][j]=f[i][i]$ 如果小球…

默认问题为 $n$ 个小球放到 $m$ 个盒子里： 球相同，盒子不同，不能有空盒 实质就是把 $n$ 个小球分为 $m$ 组（不能空）。利用插板法，就是在 $n$ 个小球的 $n-1$ 个空隙当中刚好插入 $m-1$ 个板子，即恰好分为不为空的 $m$ 组。 $$ans=\binom{n-1}{m-1}$$ 球相同，盒子不同，可以有空盒 对于每个盒…