博客园食用更佳
关注洛谷谢谢喵~
基本定义在此不再过多阐述，介绍一下基本符号：
(nm)=Cnm\dbinom{n}{m}=C_n^m(mn )=Cnm ，含义为 nnn 选 mmm 的组合方案数。
AnmA_n^mAnm ，含义为 nnn 选 mmm 的排列方案数。
求组合数方式
一般采用预处理阶乘与逆元做到线性求组合数。
如果求 (nm)\dbinom{n}{m}(mn ) 时 nnn 极大而 mmm 较小，此时无法预处理 nnn 的阶乘和逆元，可以采用下降幂运算，即预处理 mmm 的阶乘和逆元，将原式写为：
(nm)=∏i=n−m+1n×1m!\dbinom{n}{m}=\prod_{i=n-m+1}^n \times \dfrac{1}{m!} (mn )=i=n−m+1∏n ×m!1
这样就可以用较快的时间来求出组合数。
错位排列数
* 使用容斥：
Fn=∑i=0n(ni)×(n−i)!×(−1)i=n!×∑i=0n1i!×(−1)i\begin{aligned} F_n&=\sum_{i=0}^n \dbinom{n}{i} \times (n-i)! \times (-1)^i \\&=n! \times \sum_{i=0}^n \dfrac{1}{i!} \times (-1)^i \end{aligned} Fn =i=0∑n (in )×(n−i)!×(−1)i=n!×i=0∑n i!1 ×(−1)i
乘号后面进行预处理即可。
* 使用递推：设填后的序列第 iii 为 pip_ipi ，将 iii 向 pip_ipi 连边。考察 111 所在的环，设其长度为 iii。去掉 111 所在的环，剩下的数的方案数为 Fn−iF_{n-i}Fn−i 。所以枚举 iii，同时计算长度为 iii 环上的数方案数，有：
Fn=∑i=2nFn−i×(n−1)!(n−i)!=(n−1)!×∑i=0n−2Fii!\begin{aligned} F_n&=\sum_{i=2}^n F_{n-i} \times \dfrac{(n-1)!}{(n-i)!} \\&=(n-1)! \times \sum_{i=0}^{n-2} \dfrac{F_i}{i!} \end{aligned} Fn =i=2∑n Fn−i ×(n−i)!(n−1)! =(n−1)!×i=0∑n−2 i!Fi
在计算 FnF_nFn 的同时，维护乘号后面的式子。
* 依然是递推：对上文的递推进行简化，仍然考察 111 所在的环，将 111 去掉同时将环上和 111 相邻的两个点连上，等价于对后面 n−1n-1n−1 个数做错排。注意当 111 所在环只有 111 和另外一个点的时候，由于点不能指向自己，此时相当于对剩下 n−2n-2n−2 个数做错排。
还有一种理解方式，考虑现在已经有一个合法的错排图，要向里面加入一个点，则可以在任意一条边加入该点，但这样只考虑到了新加入的点所在环长度大于 222 的情况，所以还需考虑在其中取出一个点，与新加的点互相连边，剩下的点形成一张错排图。
综上有：Fn=(n−1)(Fn−1+Fn−2)F_{n}=(n-1)(F_{n-1}+F_{n-2})Fn =(n−1)(Fn−1 +Fn−2 )。
「KDOI-02」一个仇的复
观察数据范围，猜测最终时间复杂度为 O(k2)O(k^2)O(k2)。
发现方格宽度为 222，只能容下大小为 1,21,21,2 的方块竖着放，不妨将 111 看作横着放，所以只需要考虑有多少个 222 竖着放即可，设个数为 iii，对 iii 进行枚举，时间消耗为 O(k)O(k)O(k)，其中 i∈[0,k]i \in [0,k]i∈[0,k]。
现在问题化为两个子问题，一个为选竖着的 222 的方案数，一个为放完竖着的 222 后整个网格横着放的方案数。不妨先考虑第二个子问题。
先思考没有竖着的 222 的方案数。将其展开为 1×2n1 \times 2n1×2n 的平面，考虑插板，由于已经有两个基本块，所以只需要再插 k−2k-2k−2 个板，而在 nnn 与 n+1n+1n+1 之间无法插板，所以可供插板空隙为 2n−22n-22n−2，故方案数为 (2n−2k−2)\tbinom{2n-2}{k-2}(k−22n−2 )。
现在考虑有竖着的 222 情况，由于枚举了竖着的 222 的数量，设其为 iii。因为该数量固定，所以影响空隙个数的只有形成的连通块个数，设其为 jjj，则空隙个数即为 2(n−i)−2j2(n-i)-2j2(n−i)−2j。同理，可供插的板也只与连通块个数有关，为 k−i−2jk-i-2jk−i−2j。故最终方案数为 (2(n−i)−2jk−i−2j)\tbinom{2(n-i)-2j}{k-i-2j}(k−i−2j2(n−i)−2j )。故需要枚举形成连通块数量，时间消耗为 O(k)O(k)O(k)，其中，j∈[1,i+1]j \in [1,i+1]j∈[1,i+1]。
接着考虑第一个子问题。由于需要分成 jjj 个连通块，所以用来分隔网格的竖着的 222 的连通块个数即为 j−1j-1j−1。但是如果竖着的 222 放在了开头或者末尾是不会影响网格连通块个数的，所以 222 连通块个数还可以为 j,j+1j,j+1j,j+1。对这个问题做插板，发现可以插 j+1j+1j+1 个板，而可供插板的空隙为 iii 个的开头结尾和中间共计 i+1i+1i+1 个位置。所以该问题方案数为 (i+1j)\tbinom{i+1}{j}(ji+1 )。
最后考虑放着这些连通块到网格的方案数，相当于将剩下的 2×(n−i)2 \times (n-i)2×(n−i) 个格子分为 jjj 块，仍然用插板法，得知方案数为 (n−i−1j−1)\tbinom{n-i-1}{j-1}(j−1n−i−1 )。
发现有一种情况没有考虑，即 n=kn=kn=k 时选 kkk 个竖着的 222 的方案，这种情况无法刻画，因为没有形成连通块，最后特判加上即可。
最终答案为：
∑i=0k∑j=1i+1(2n−2i−2jk−i−2j)×(i+1j)×(n−i−1j−1)+[n=k]=∑i=0k∑j=0i(2n−2i−2j−2k−i−2j−2)×(i+1j+1)×(n−i−1j)+[n=k]\begin{aligned} \\& \sum_{i=0}^k \sum_{j=1}^{i+1} \tbinom{2n-2i-2j}{k-i-2j} \times \tbinom{i+1}{j} \times \tbinom{n-i-1}{j-1} + [n=k]\\&= \sum_{i=0}^k \sum_{j=0}^{i}
\tbinom{2n-2i-2j-2}{k-i-2j-2} \times \tbinom{i+1}{j+1} \times \tbinom{n-i-1}{j} +[n=k]\end{aligned} i=0∑k j=1∑i+1 (k−i−2j2n−2i−2j )×(ji+1 )×(j−1n−i−1 )+[n=k]=i=0∑k j=0∑i (k−i−2j−22n−2i−2j−2 )×(j+1i+1 )×(jn−i−1 )+[n=k]
可能空间开不下，但是发现可以预处理后两个组合数的阶乘和逆元，对前一个组合数只预处理阶乘，求的时候现求逆元即可（或者都开成 intintint，强转 longlonglong longlonglong）。
广义组合数
* 当 n≥m≥0n \ge m \ge 0n≥m≥0 时，(nm)=n!(n−m)!m!\dbinom{n}{m}=\dfrac{n!}{(n-m)!m!}(mn )=(n−m)!m!n!
* 当 m≥0∧m≥nm \ge 0 \land m \ge nm≥0∧m≥n 时，(nm)=∏i=n−m+1nim!\dbinom{n}{m}=\dfrac{\prod_{i=n-m+1}^n i}{m!}(mn )=m!∏i=n−m+1n i
* 由二式得，当 m≥n≥0m \ge n \ge 0m≥n≥0 时，有：
(−nm)=∏i=−n−m+1−nim!=(n+m−1)!(n−1)!m!×(−1)m=(−1)m×(n+m−1m)\begin{aligned} \dbinom{-n}{m}&=\dfrac{\prod_{i=-n-m+1}^{-n} i}{m!}\\&=\dfrac{(n+m-1)!}{(n-1)!m!} \times (-1)^m\\&=(-1)^m \times \dbinom{n+m-1}{m} \end{aligned} (m−n ) =m!∏i=−n−m+1−n i =(n−1)!m!(n+m−1)! ×(−1)m=(−1)m×(mn+m−1 )
[集训队互测 2012] CALC
首先可以做一个简单的 dp，dpi,jdp_{i,j}dpi,j 表示考虑 [1,i][1,i][1,i] 中的数，选了 jjj 个数在序列中的权值积，最后 dpk,n×n!dp_{k,n} \times n!dpk,n ×n! 即为答案。
观察 dp 转移：dpi,j=dpi−1,j+dpi−1,j−1×idp_{i,j} = dp_{i-1,j} + dp_{i-1,j-1} \times idpi,j =dpi−1,j +dpi−1,j−1 ×i，发现转移系数和 iii 有关，故矩阵快速幂中的转移矩阵不固定，没有前途。
本题生成函数对于笔者来说太过困难，所以在此只讨论使用拉插解题。
发现 dp 转移非常简洁，所以猜测对于固定的 jjj，dpi,jdp_{i,j}dpi,j 在一个多项式上。设 g(fx)g(f_x)g(fx ) 表示 fxf_xfx 的多项式次数，则显然有，g(fx−fx−1)=g(fx)−1g(f_x-f_{x-1})=g(f_x)-1g(fx −fx−1 )=g(fx )−1。观察 dp 转移式子，有：
dpi,j=dpi−1,j+dpi−1,j−1×idpi,j−dpi−1,j=dpi−1,j−1g(fj)−1=g(fj−1)+1\begin{aligned} &dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1} \times i \\&dp_{i,j}-dp_{i-1,j}=dp_{i-1,j-1} \\&g(f_j)-1=g(f_{j-1})+1 \end{aligned} dpi,j =dpi−1,j +dpi−1,j−1 ×idpi,j −dpi−1,j =dpi−1,j−1 g(fj )−1=g(fj−1 )+1
又因为 g(f0)=0g(f_0)=0g(f0 )=0 次，所以 g(fj)=2jg(f_j)=2jg(fj )=2j。因此只需要做 2n+12n+12n+1 次 dp，然后拉插即可。
[JLOI2015] 骗我呢
发现值域为 [0,m][0,m][0,m]，则一行只有一个位置会 +2+2+2，可以做出来简单 dp，优化过后变为 dpi,j=dpi,j−1+dpi−1,j+1dp_{i,j}=dp_{i,j-1}+dp_{i-1,j+1}dpi,j =dpi,j−1 +dpi−1,j+1 。
代数推导一点不会，组合意义天崩地裂。
发现式子很简洁，想用上一题的方法看看多项式，发现次数为 nnn，那肯定没救的。所以考虑组合意义，将其放在网格图上，考虑将 dp 值变为到达 (i,j)(i,j)(i,j) 的路径条数，dp 转移看为一条边。发现转移中有斜着的边，不好处理，所以将其平移。发现行末仍然有一条斜边，将其扩展为先向右再向下，于是得到一张网格图。由于将每一行行末扩展了，所以每一行长度为 m+1m+1m+1，则问题变为在网格图上，从原点出发，到达 (n+m+1,n)(n+m+1,n)(n+m+1,n) 的方案数，网格形状如下：
将网格形状转化为限制，变为不接触两条直线的方案数。称直线 AAA 为上方直线，直线 BBB 为下方直线，点 PPP 为 (n+m+1,n)(n+m+1,n)(n+m+1,n)。考虑反射容斥，即将总方案数即从原点到 PPP 的路径数，减去碰到任意一条直线且可能越过直线的方案数，将碰到的直线依次写为一个序列，相邻相同的直线进行缩点，最后会得到 ⋯ABAB\cdots ABAB⋯ABAB 或 ⋯BABA\cdots BABA⋯BABA，将不合法方案分为末尾为 AAA 的方案和末尾为 BBB 的方案。发现将 PPP 沿直线 AAA 对称得到 P′P'P′ 后，每一条从原点到达 P′P'P′
的路径都可以通过从第一次接触 AAA 开始对称，最终到达 PPP；同理，每一条从原点到达 PPP 且接触了 AAA 的路径都可以从第一次接触 AAA 开始对称，最后到达 P′P'P′，所以形成了双射。考虑这类方案对应接触序列是怎样的。考虑到达 PPP 且接触 AAA 的路径中从最后一次接触 AAA 到 PPP 的路径，由于为最后一次接触 AAA，所以不会再碰到 AAA，只有可能碰到 BBB。所以这类路径个数对应序列结尾为 AAA 或 ABABAB 的序列个数；同理，若将 PPP 沿 BBB 反转，可以得到序列结尾为 BBB 或 BABABA 的序列个数。发现总共多减去结尾为 ABABAB 和
BABABA 的序列个数。考虑将 P′P'P′ 再次沿 BBB 对折，仍然考虑从原点到 P′′P''P′′ 的路径中最后一次接触 BBB 来看，后面一定会接触 AAA，然后可能在去往 PPP 的路径上再次接触 BBB，所以路径末尾为 BABABA 或 BABBABBAB。
所以有一个简单的容斥，发现 P,P′,P′′⋯P,P',P'' \cdotsP,P′,P′′⋯ 形成的直线斜率为 −1-1−1，每两次对称一定会向 x,yx,yx,y 轴移动，所以至多移动线性次，所以时间复杂度为线性。
第一类斯特林数
s(n,k)s(n,k)s(n,k) 表示 nnn 个数，分为 kkk 个环（即 1,2,3,41,2,3,41,2,3,4 与 4,1,2,34,1,2,34,1,2,3 算一种方案）的方案数，记作 [nm]\displaystyle {n \brack m}[mn ]。
有递推式：s(n,k)=s(n−1,k−1)+s(n−1,k)×(n−1)s(n,k)=s(n-1,k-1)+s(n-1,k) \times (n-1)s(n,k)=s(n−1,k−1)+s(n−1,k)×(n−1)。代表新加入的点是新增一个环还是插入到原有的环中共 (n−1)(n-1)(n−1) 个位置中。
有性质：
* s(n,1)=(n−1)!s(n,1)=(n-1)!s(n,1)=(n−1)!，易证。
* s(n,2)=(n−1)!×∑i=1n−11is(n,2)=(n-1)! \times \sum_{i=1}^{n-1} \dfrac{1}{i}s(n,2)=(n−1)!×∑i=1n−1 i1 ，证明考虑数学归纳法。
* ∑k=1ns(n,k)=n!\sum_{k=1}^n s(n,k)=n!∑k=1n s(n,k)=n!。考虑任意一个排列都可以通过 i→aii \to a_ii→ai 连边来映射成唯一一个由若干个环组成的图；同理，环也可以映射成唯一一个排列。二者形成双射。
下降幂
有 xi‾=x!(x−i)!x^{\underline i}=\dfrac{x!}{(x-i)!}xi =(x−i)!x! 。文章开头即为下降幂优化求组合数式子。
其与组合数相乘有着优雅的形式，如下：
(nk)×km‾=n!(n−k)!(k−m)!=(n−m)!(n−k)!(k−m)!×n!(n−m)!=(n−mn−k)×nm‾\begin{aligned} \dbinom{n}{k} \times k^{\underline m} &= \dfrac{n!}{(n-k)!(k-m)!}\\&=\dfrac{(n-m)!}{(n-k)!(k-m)!} \times \dfrac{n!}{(n-m)!}\\&=\dbinom{n-m}{n-k} \times n^{\underline m} \end{aligned} (kn )×km =(n−k)!(k−m)!n!
=(n−k)!(k−m)!(n−m)! ×(n−m)!n! =(n−kn−m )×nm
发现原本式子中两个乘数都含有 kkk，转化完后只有一个式子含有 kkk。
第二类斯特林数
S(n,k)S(n,k)S(n,k) 表示 nnn 个数，分为 kkk 组，每组无序，组与组之间没有区别的方案数，记作 {nm}\displaystyle {n \brace m}{mn }。
有递推式：S(n,k)=S(n−1,k−1)+S(n−1,k)×kS(n,k)=S(n-1,k-1)+S(n-1,k) \times kS(n,k)=S(n−1,k−1)+S(n−1,k)×k。代表新加入的点是新增一组还是加入原有的 kkk 组中。
第二类斯特林数可用于转化幂：xn=∑i=1n{ni}xi‾x^n=\sum_{i=1}^n \displaystyle {n \brace i} x^{\underline{i}}xn=∑i=1n {in }xi ，证明考虑数学归纳法：
xn=x×xn−1=x×∑i=1n−1{n−1i}xi‾=∑i=1n−1{n−1i}xi‾(x−i)+∑i=1n−1{n−1i}xi‾i=∑i=1n−1{n−1i}xi+1‾+∑i=1n{n−1i}xi‾i=∑i=1n{n−1i−1}xi‾+∑i=1n{n−1i}xi‾i=∑i=1n{ni}xi‾\begin{aligned} x^n&=x \times x^{n-1}\\&=x \times \sum_{i=1}^{n-1} \displaystyle {n-1 \brace i} x^{\underline i}\\&=\sum_{i=1}^{n-1} \displaystyle {n-1
\brace i} x^{\underline i} (x-i) + \sum_{i=1}^{n-1} \displaystyle {n-1 \brace i} x^{\underline i} i\\&=\sum_{i=1}^{n-1} \displaystyle {n-1 \brace i} x^{\underline {i+1}} + \sum_{i=1}^n \displaystyle {n-1 \brace i}x^{\underline i} i\\&=\sum_{i=1}^n \displaystyle {n-1 \brace i-1} x^{\underline i} +
\sum_{i=1}^n \displaystyle {n-1 \brace i} x^{\underline i} i\\&=\sum_{i=1}^n \displaystyle {n \brace i} x^{\underline i} \end{aligned} xn =x×xn−1=x×i=1∑n−1 {in−1 }xi =i=1∑n−1 {in−1 }xi (x−i)+i=1∑n−1 {in−1 }xi i=i=1∑n−1 {in−1 }xi+1 +i=1∑n {in−1 }xi i=i=1∑n {i−1n−1 }xi +i=1∑n {in−1 }xi i=i=1∑n {in }xi
[省选联考 2020 A 卷] 组合数问题
发现原式为 kkk 的次幂乘上关于 kkk 的组合数，因为 kkk 很大，不能枚举，这个形式有不是那么好看，所以使用下降幂来将其优化一下。将原多项式变为下降幂多项式，设 f(x)=∑i=0mbiki‾f(x)=\sum_{i=0}^m b_i k^{\underline i}f(x)=∑i=0m bi ki ，然后开始转化：
∑k=0nf(k)xk(nk)=∑k=0n∑i=0mbiki‾xk(nk)=∑k=0n∑i=0mbi(n−ik−i)ni‾xk=∑i=0mbini‾∑k=0n−i(n−ik)xk+i=∑i=0mbini‾xi∑k=0n−1(n−ik)xk=∑i=0mbini‾xi(x+1)n−i\begin{aligned} &\sum_{k=0}^n f(k) x^k \dbinom{n}{k}\\=&\sum_{k=0}^n\sum_{i=0}^m b_i k^{\underline i} x^k \dbinom{n}{k}\\=&\sum_{k=0}^n \sum_{i=0}^m b_i
\dbinom{n-i}{k-i} n^{\underline i} x^k \\=& \sum_{i=0}^m b_i n^{\underline i} \sum_{k=0}^{n-i} \dbinom{n-i}{k} x^{k+i}\\=&\sum_{i=0}^m b_i n^{\underline i} x^i \sum_{k=0}^{n-1} \dbinom{n-i}{k} x^k\\=&\sum_{i=0}^m b_i n^{\underline i} x^i (x+1)^{n-i} \end{aligned} ===== k=0∑n f(k)xk(kn )k=0∑n i=0∑m
bi ki xk(kn )k=0∑n i=0∑m bi (k−in−i )ni xki=0∑m bi ni k=0∑n−i (kn−i )xk+ii=0∑m bi ni xik=0∑n−1 (kn−i )xki=0∑m bi ni xi(x+1)n−i
则问题转化为求 bib_ibi 。
因为有 xn=∑i=0n{ni}xi‾x^n=\sum_{i=0}^n \displaystyle {n \brace i} x^{\underline i}xn=∑i=0n {in }xi ，所以将 f(x)f(x)f(x) 进行转化：
f(x)=∑i=0maixi=∑i=0mai∑j=0i{ij}xj‾=∑i=0mxi‾∑j=imaj{ji}\begin{aligned} f(x)&=\sum_{i=0}^m a_i x^i\\&= \sum_{i=0}^m a_i \sum_{j=0}^i \displaystyle {i \brace j} x^{\underline j}\\&=\sum_{i=0}^m x^{\underline i} \sum_{j=i}^m a_j \displaystyle {j \brace i} \end{aligned} f(x) =i=0∑m ai xi=i=0∑m ai j=0∑i
{ji }xj =i=0∑m xi j=i∑m aj {ij }
可以递推预处理出所有第二类斯特林数，然后 O(m2)O(m^2)O(m2) 求出所有 bib_ibi ，最后 O(m2)O(m^2)O(m2) 求出答案。
总时间复杂度 O(m2)O(m^2)O(m2)。
