第二类斯特林数

S(n,m):n个点分成m个相同集合

带入定义,递推式为S(n,m)=S(n1,m1)+mS(n1,m)

转化xn

xn的组合意义是把n个点随意放到x个不同位置里,枚举那些位置放了点,则

xn=0xC(x,i)i!S(n,i)

有一些涉及到xn(x+1)n可以展开之后带入递推式快速转移

容斥/二项式反演得到

S(n,m)=i=0m(1)miC(m,i)inm!

S(n,m)的通项公式

下降幂多项式卷积

xn_=x!(xn)!

下降幂多项式F(x)EGF

EGF(F(x))=i=0xii!j=0ni!(ij)!Fj

EGF(F(x))=i=0xij=0n1(ij)!Fj

换一下顺序

EGF(F(x))=i=0nFij=i1(ji)!xj

EGF(F(x))=i=0nFixij=01j!xj

EGF(F(x))=i=0nFixiex

那么直接卷积就可以得到F(x)EGF,然后点值对应相乘

卷回来的时候

EGF(F(x))=i=0nFixiex

Fi=EGF(F(x))xiex

那么就直接卷上ex就可以了

普通多项式转下降幂多项式

带入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)jkC(j,k)kij!

G(x)=[xi]F(x)xj_(1)jkkik!(jk)!

是一个三元的卷积优化,比较复杂

ij,[xj_]G(x)=(1)jk[xi]F(x)ki(jk)!k!

考虑分步优化

Part1 ik

先计算出H(k)=[xi]F(x)ki

发现[xi]H(x)=F(i),多项式多点求值得到

Part2 kj

对于已经得到的H(x)

[xj_]G(x)=(1)jk[xk]H(x)k!(jk)!

可以直接卷积得到

下降幂多项式转普通多项式

求出F(x)EGF,然后带入前n项的值,快速插值回来即可