第二类斯特林数
S(n,m):n个点分成m个相同集合
带入定义,递推式为S(n,m)=S(n−1,m−1)+m⋅S(n−1,m)
转化xn
xn的组合意义是把n个点随意放到x个不同位置里,枚举那些位置放了点,则
xn=x∑0C(x,i)i!S(n,i)有一些涉及到xn→(x+1)n可以展开之后带入递推式快速转移
容斥/二项式反演得到
S(n,m)=∑mi=0(−1)m−iC(m,i)inm!即S(n,m)的通项公式
下降幂多项式卷积
xn––=x!(x−n)!
下降幂多项式F(x)的EGF是
EGF(F(x))=∑∞i=0xii!∑nj=0i!(i−j)!⋅Fj
EGF(F(x))=∑∞i=0xi∑nj=01(i−j)!⋅Fj
换一下顺序
EGF(F(x))=∑ni=0Fi∑∞j=i1(j−i)!xj
EGF(F(x))=∑ni=0Fi⋅xi∑∞j=01j!xj
EGF(F(x))=∑ni=0Fi⋅xiex
那么直接卷积就可以得到F(x)的EGF,然后点值对应相乘
卷回来的时候
EGF(F(x))=∑ni=0Fi⋅xiex
Fi=EGF(F(x))xiex
那么就直接卷上e−x就可以了
普通多项式转下降幂多项式
带入xn的第二类斯特林数展开式,xn=∑C(x,i)i!S(n,i)=∑xi–S(n,i)
G(x)=∑[xi]F(x)∑xj–S(i,j)
G(x)=∑[xi]F(x)∑xj–∑(−1)j−kC(j,k)kij!
G(x)=∑[xi]F(x)∑xj–∑(−1)j−kkik!(j−k)!
是一个三元的卷积优化,比较复杂
i→j,[xj–]G(x)=(−1)j−k[xi]F(x)ki(j−k)!k!
考虑分步优化
Part1 i→k
先计算出H(k)=∑[xi]F(x)ki
发现[xi]H(x)=F(i),多项式多点求值得到
Part2 k→j
对于已经得到的H(x)
[xj–]G(x)=∑(−1)j−k[xk]H(x)k!(j−k)!
可以直接卷积得到
下降幂多项式转普通多项式
求出F(x)的EGF,然后带入前n项的值,快速插值回来即可