Hi everyone!

Previously, I had a blog on how, given $$$s$$$ and a polynomial $$$f(x)$$$, to compute coefficients of the polynomial $$$f(x+s)$$$.

Today we do it in values space. Consider the problem Library Judge — Shift of Sampling Points of Polynomial. In this problem, you're given $$$s$$$ and the values $$$f(0), f(1), \dots, f(n)$$$ of a polynomial of degree at most $$$n$$$ and you need to find $$$f(s), f(s+1), \dots, f(s+n)$$$.

In particular, I used this to generate test cases for 1817C - Подобные многочлены, there might be other applications too.

General linear recurrence shift

If you have further questions about something here, please refer to this blog

Let's, for a moment, consider even more generic problem now. Let $$$f_0, f_1, \dots$$$ be a linear recurrence, such that

Given $$$s$$$ and $$$f_0, \dots, f_n$$$, we need to find $$$f_s, \dots, f_{s+n}$$$. The problem generalizes that of finding specific value $$$f_s$$$.

Generally, we can say that $$$f_s, \dots, f_{s+n}$$$ are the coefficients near $$$x^0, x^{-1}, \dots, x^{-n}$$$ of $$$x^s g(x^{-1})$$$, where

is the generating function of $$$f_k$$$. On the other hand, $$$g(x) = \frac{p(x)}{q(x)}$$$, where

and $$$p(x)$$$ is a polynomial of degree at most $$$n$$$. Let

then $$$D(x) g(x^{-1}) = x^{n+1} p(x^{-1})$$$ only has positive powers of $$$x$$$ if $$$D(x)$$$ is divisible by $$$A(x)$$$. Thus, the coefficients near non-positive powers of $$$x^s g(x^{-1})$$$ will not change if we replace $$$x^s$$$ by its remainder modulo $$$A(x)$$$. So, we need coefficients near $$$x^0, x^{-1}, \dots, x^{-n}$$$ of the product $$$R(x) g(x^{-1})$$$, where $$$R(x) \equiv x^s \pmod{A}$$$. Note that only the first $$$2n+1$$$ coefficients of $$$g(x)$$$ affect the result, hence the whole problem may be solved in $$$O(n \log n \log s)$$$ for finding $$$R(x)$$$ and then $$$O(n \log n)$$$ to find $$$f_s, \dots, f_{s+n}$$$.

If you're not comfortable working with negative coefficients, a possibly simpler way to look on it is to notice that

On the other hand, changing the first polynomial to $$$f_1 x^{n+1} + \dots + f_{n+2}$$$ would yield $$$f_{m+1}$$$ as a result. Altogether, it means that

would yield the values $$$f_{s+n}, \dots, f_{s+1}, f_s$$$ in its coefficients near $$$x^{n+1}, x^{n+2}, \dots, x^{2n+1}$$$.

Shift in polynomials

In polynomials, it is possible to implement the solution above in $$$O(n \log n)$$$ instead of $$$O(n \log n \log s)$$$. For this we should note that $$$f(0), f(1), \dots$$$ also form a linear recurrence with a very specific characteristic polynomial $$$q(x) = (1-x)^{n+1}$$$.

Perhaps the simplest way to show it is by noticing that taking finite difference $$$\Delta f(k) = f(k) - f(k-1)$$$ for $$$n+1$$$ times will yield a zero polynomial, as $$$\Delta$$$ reduces the degree by $$$1$$$. Using a function $$$S$$$ such that $$$S f(k) = f(k-1)$$$, we can write it as

which shows that $$$(1-x)^{n+1}$$$ is the characteristic polynomial of the corresponding recurrence. Thus,

can be transformed via substitution $$$x = t+1$$$ into

The identity above allows us to find

from which we can obtain the final result by substituting $$$t=x-1$$$ back

which can then be computed as a regular Taylor shift by $$$-1$$$ of $$$R(t+1)$$$ in $$$O(n \log n)$$$.

You can also refer to my solution on the Library Judge.

UPD: It was brought to my attention that $$$R(x)$$$ can be computed in linear time, as

Then, using $$$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$$, we transform the later sum into a telescopic one:

Thus, the full expression for $$$R(x)$$$ is

UPD2: Golovanov399 mentioned in the comments that there is a much simpler way of doing it for polynomials using the representation

of the generating function. As $$$(1-x)^{n+1}$$$ is a very well-behaved function, one may notice that

then one can find $$$f(s), \dots, f(s+n)$$$ by multiplying $$$p(x)$$$, which is obtained as

with the corresponding segment of coefficients of $$$(1-x)^{-(n+1)}$$$ near the $$$s$$$-th coefficient.

UPD3: It was brought to my attention that it is possible to do this in just a single convolution. Upon some further discussion with Golovanov399, we found out that the Lagrange interpolation on $$$f(0), \dots, f(n)$$$ can actually be written simply as

In particular, it also gives a much simpler and more concise expression for $$$R(x)$$$ from above:

We also derived the following formula:

Applying the function $$$T(y^i) = f(i)$$$ to it, we get the identity for $$$k \geq 1$$$:

which allows to find $$$f(s), \dots, f(s+n)$$$ in a single convolution with a sub-range of the coefficients of $$$\log\frac{1}{1-x}$$$.

The result above can also be found directly from manipulating coefficients in Lagrange interpolation formula. I kind of like it, but unfortunately we do not yet know if there is any meaningful interpretation to the result in terms of $$$x$$$ and $$$y$$$.

Questions to audience

• Is there a simpler solution here, preferably without heavy low-level work with coefficients...
• Is it possible to compute $$$R(x)$$$ directly, rather than as a Taylor shift?
• Are there other viable applications to doing this?