正题
我们来考虑这个东西如何用与k相关的时间快速计算.
我们记
我们构造其关于k的EGF,则有:
可以发现这是一个等比数列求和的形式,那么就有:
接着,我们将其表示为拆成两部分
可以观察到,后面的那一部分,相当于
因为EGF自带一个i!的系数,这个EGF十分有规律,可以求
而前边一部分貌似就没那么有规律了,我们将它们设为
而这个序列B就被称为伯努利数.
同时,因为是EGF卷积的形式,我们可以将它们通过式子写出来:
伯努利数显然可以通过多项式求逆的方式得到,然后就可以用O(k)的时间求出S(n,k)或者用O(k log k)的时间求出S(0,k),...,S(n,k)
同时我们也得到了0~n-1的自然数k次幂和与n^{0,..,k+1}的关系