Please subscribe to the official Codeforces channel in Telegram via the link ×

[Tutorial] Prefix Sum Polynomial

Revision en1, by Lain, 2022-01-01 10:06:10

Consider the $$$n$$$ degree polynomial $$$P(x) = \sum_{i=0}^n p_ix^i$$$. I call the polynomial $$$Q(x)$$$ it's "prefix sum polynomial" if it satisfies the following condition:

$$$ Q(x) = \sum_{y=0}^x P(y) $$$

Essentially, $$$Q(x)$$$ is a prefix sum on the values of $$$P(x)$$$. So,

$$$ \begin{aligned} Q(x) &= \sum_{y=0}^x P(y) \\ &= \sum_{y=0}^x \sum_{i=0}^n p_i y^i \\ &= \sum_{i=0}^n p_i \sum_{y=0}^x y^i \end{aligned} $$$

Now, all we need is a formula for the prefix sum of $$$y^i$$$. This is given by Faulhaber's Formula:

$$$ \sum_{y=0}^x y^i = \frac{1}{i+1} \sum_{j=0}^i \binom{i+1}{j} B_j x^{i+1-j} $$$

where $$$B_j$$$ is the $$$j$$$th Bernoulli number. The formula only applies for positive values of $$$i$$$, so we have to handle $$$[x^0]P(x)$$$ separately. Moreover, we can tell from this formula that the degree of $$$Q(x)$$$ will be $$$n+1$$$.

Just using the formula above is enough to find $$$Q(x)$$$ in $$$O(n^2)$$$, but let us go further. From what we know so far, the coefficients of $$$Q(x)$$$ would be:

$$$ \begin{aligned} [x^i]Q(x) &= \sum_{j=i-1}^n \frac{p_j}{j+1} B_{j+1-i} \binom{j+1}{j+1-i} \\ &= \sum_{j=i-1}^n \frac{p_j}{j+1} B_{j+1-i} \frac{(j+1)!}{i! \cdot (j+1-i)!} \\ &= \frac{1}{i!} \sum_{j=i-1}^n (p_j j!) \cdot \frac{B_{j+1-i}}{(j+1-i)!} \\ \end{aligned} $$$

This looks suspiciously like a convolution. Let us define $$$A(x)$$$ and $$$B(x)$$$ as:

$$$ A(x) = \sum_{i=0}^n \frac{B_{n-i}}{(n-i)!} x^i $$$
$$$ B(x) = \sum_{i=1}^n (p_i \cdot i!)x^i $$$


$$$ [x^i] Q(x) = \frac{[x^{i+n-1}](A \cdot B)}{i!} $$$

We can include the contribution of $$$[x^0]P(x)$$$ after this by adding it to $$$[x^0]Q(x)$$$ and $$$[x^1]Q(x)$$$. This way, we can calculate $$$Q(x)$$$ in $$$O(n \log n)$$$ using FFT.

Finally, we need to tackle the problem of calculating the Bernoulli numbers. We could use the recursive formula on the Wikipedia page, but that's $$$O(n^2)$$$. Instead, we can use the exponential generating function of the Bernoulli numbers:

$$$ \frac{x}{e^x-1} = \left(\sum_i \frac{x^i}{(i+1)!} \right)^{-1} $$$

Now, we can solve the entire problem in $$$O(n \log{n})$$$.

I'd like to thank neal since I only found this technique by looking at his submission for ARC 104 E. I later found out that this same idea is used in the problem SERSUM by chemthan, but I decided to make the blog anyway to introduce it to more people.

Tags polynomials, fft


  Rev. Lang. By When Δ Comment
en5 English Lain 2022-01-02 09:06:57 176 Added blog
en4 English Lain 2022-01-01 10:23:20 0 (published)
en3 English Lain 2022-01-01 10:17:27 1
en2 English Lain 2022-01-01 10:15:14 20
en1 English Lain 2022-01-01 10:06:10 2627 Initial revision (saved to drafts)