第一类斯特林数
定义是 (n) 个数,(m) 个圆排列
(Theta(n^2)) 的 (dp) 是:(S_{i,j}=S_{i-1,i-1}+S_{i-1,j} imes (i-1))
如果预处理一行的话需要这个式子:
分治乘法做到 (Theta(nlog^2n)),更快的部分需要倍增
也就是 (x^{overline{2n}}=x^{overline{n}}(x+n)^{overline{n}})
考虑 (f(x)) 来推 (f(x+c)) 是可以做的,那么直接两个卷积即可
注意减法卷积贡献到的位置,是 (len+i+1)
对于求一列的情况,考虑 (EGF):(S_1) 的 (EGF) 是 (sum_{i} frac{x^{i}}i)
对于多个圆排列就快速幂一下,最后要除掉圆排列个数因为其本质相同
写一个 (ln+exp) 即可
第二类斯特林数
定义第二类斯特林数 (S(n,m)) 为将 (n) 个球放到 (m) 个盒子里的方案数,球不同,盒子相同
然后容易由 (dp) 得到一个递推式
按照组合意义:容斥有多少个盒子是空的
把式子推一下
这里是个卷积,预处理阶乘,逆元就做完了
第二类斯特林数的一个性质:
直接上组合意义,左边是在 (n) 个互不相同盒子里面放 (k) 个小球的方案
右边是枚举盒子的数量,放在哪几个盒子里面,然后因为盒子不一样,然后就在来个阶乘就没了
如果是求一列,考虑设第 (i) 列的普通生成函数为 (S_i(x))
不难观察到其只和自己和上一列有关,递推式就是 (S_i(x)=mx imes S_i(x)+S_{i-1}(x) imes x)
不断迭代下去得到
分治乘法加求逆即可,也可以按照 (EGF) 来做
例题
HEOI2016 求和
首先把三角转成矩形,然后套上 第二类斯特林数的组合公式,每一步都找无关量,最后推等差出来卷积即可
(Theta(n)) 的做法当然不是现在学的
「Luogu4827」 Crash的文明世界
记住这个关键的式子:
使用人类智慧,把最后的组合数用杨辉三角展开(其实用“如何转移”的思路也可以得到)
那么设 (f_{x,i}) 表示 (x) 为根的时候子树里面 (inom {dis} i) 的和
换根统计即可