正题

      我们来考虑这个东西如何用与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}的关系

      伯努利数的递推式:

      可以这样构造,后半部分的EGF序列很有规律,就是

      那么就有