Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

[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$

Then,

$[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.

#### History

Revisions

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