(S(n) = sumlimits_{i<=n} i^ka^i)
这个式子来源于SP19997。
鱼神的题解里提到，(S(n))这样的式子，可以写成更通用的形式：
(S(n) = sum f(i)a^i (i <= n),)在本题中，(f(i) = i^k)
同时也有一个窝不会证明的神仙结论：
存在一个次数不高于 (k) 的多项式 (g(x))，使得 (S(n)=a^ng(n)-g(0))
也就是说，我们只要知道(g(n))和(g(0)),就可以快速求出这个式子。
然后我们很容易推得 (g(n)=(g(n-1)+f(n-1))/a)
又因为(g(n))是(k)次多项式，所以(k+1)次差分后其必然是(0),即
(sumlimits_{i=0}^{k+1}(-1)^iinom{k+1}{i}g(k+1-i)=0)
然后设个未知数，把(g(0)...g(k))都解出来，就可以插值求出(g(n))了
然后就没了。
复杂度(O(k))
(upd) (on) (2020.4.28:)
为什么这个做法有时候会出锅呢(?)
主要是因为这个做法设未知数解方程的过程中可能出现
(ax=c,a=0,c eq 0)的情况或者(ax=c,a=0,c=0)的情况(.)
这时候一般来说是可以特判的(,)比如说当(f(i) = i^0 = 1)的时候就可以直接(O(k))插值做自然数幂和(.)