Hi there! Imagine you're participating in codechef long challenge and you see a problem from chemthan asking you to calculate some sums of powers like 1^{p} + 2^{p} + ... + *n*^{p} for all *p* from 0 to *k*. You immediately understand what's going on here and take Faulhaber's formula from your wide pants, do ya? Just take a look at it!

Beautiful, right? Wrong! This formula is dumb and it's hard to understand and remember! Why would you ever think about Bernoulli's number on any contest which lasts less than a week? And what the hell are those Bernoulli numbers?! Here is what you should do:

Let *S*_{p} = 1^{p} + ... + *n*^{p}. Consider its exponential generating function (EGF):

Now you can simply find *S*_{0}, ..., *S*_{k} by finding inverse series for and multiplying it with . Enjoy your power sums without Stirling and/or Bernoulli numbers!

Exercise: Solve this problem in .

P.S. Yes, you basically perform the same calculations as in Faulhaber's formula, but now you hopefully understand what you're doing.

First of all, you don't need to remember Faulhaber's formula, you only need to know that it exists and interpolate.

Also, these solutions are substantially different, because Faulhaber's formula finds

S_{p}(n) for fixedpand alln, and yours finds it for fixednand allp.I don't really agree with you here because calculating inverse to you calculate nothing but EGF for Bernoulli numbers so approaches are exactly the same, but with different interpretation.

And I think, you should be more precise about what do you mean by all

n. If it's allnfrom 1 toNthen you don't seem to need any special formulas at all, you can calculate it in . If you mean fixedpand arbitrary singlenthen my solution allows you to do so as well.And yes, you're right, interpolation also allows to solve this particular case with both

nandpfixed inO(p). But as you may see at the beginning of my post, I wanted to write specifically about case whennis fixed and you need to calculate values for allpfrom 0 tok.I understand that it might be a bit misguiding since I only paste formula here without further comments, but it was supposed to be considered as convolution:

So in this interpretation you clearly may calculate values for all p.

Sorry, I forgot that evaluating polynomial takes

O(p) time which is not even better than interpolation.I got that your solution works for all

pfor 0 tok. But still, for fixednandp, I don't see a way to make it work in linear time, like interpolation. Calculating single coefficient of product is easy, but here we have quotient. So it seems, your solution is only good when we need to calculate the sum for differentp. In other cases additional logarithm with pretty big constant from inverse seems bad.That is true, for fixed

nandpLagrange interpolation is better. Though it worth mentioning that you seemingly can't apply interpolation in this problem while similar EGF can be calculated in to solve the problem.How to find inverse series? I know there is a post by vfleaking on codeforces on the same.I read it several times but still I can't understand . Please tell me ,how can we find inverse series?

link

Here. Read editorial part for problem E from the line "_There is an interesting algorithm which calculate the inverse of a power series F(z)_ "

I have paragraph about it here.

i am thinking of Maclaurin expansion for finding inverse series for (1-e^x)/x but it's hard to implement is there any other way to do this

using some complex analysis

this problem too but here lagrange interpolation is much better https://codeforces.com/contest/622/problem/F

It should follow from these expressions that for

p≥ 0The first three cases are:

p= 0:S_{0}=np= 1:S_{0}+ 2S_{1}=n^{2}+ 2n, andp= 2:S_{0}+ 3S_{1}+ 3S_{2}=n^{3}+ 3n^{2}+ 3n, andTherefore, the following recursive expression can be derived for

p≥ 1where the base case is

S_{0}=nYep, there is this formula but you can't calculate fast enough with it.

I wonder why this recursive formula may not be fast enough for modular arithmetic with large

nand smallp, as both (n+ 1)^{p + 1}and may be computed recursively in reasonable time whenpis small. Furthermore, the division by (p+ 1) operation may be preformed using modular multiplicative inverse. Any plausible explanation for such presumed inefficiency would be appreciated.Because you'll have to compute each of

S_{j}forjfrom 0 top.But isn't it required in the problem statement to compute

S_{p}for allpfrom 0 tok? It seems that the only difference between both requirements is the change in the parameter names.I'd just like to clarify a doubt — Is it possible to solve these types of sums using Lagrange interpolation ?

Yes, but only if you have to calculate it for single fixed

nandp.Thanks for clarifying :)

Finally nice and short text about it! You are definitely my favorite blog writer since now :D Big +

Great to see such feedback! Now you really have to learn Russian so you can enjoy even more of my blogs X)