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 - Similar Polynomials, 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?

bro really wants the top contributors' first spot

adamant got that "obscure math blogs" pipeline working overtime

[there was a mistake in the text here which I can't seem to fix]

[redacted]

I don't understand. If you know that your recurrence is $$$p(x) / (1-x)^n$$$, then you can find $$$p(x)$$$ by multiplying the recurrence by $$$(1-x)^n$$$ and dropping the coefficients above the $$$n$$$-th. Then, to find the values from some $$$s$$$-th, you divide by $$$(1-x)^s$$$ or something, which is multiplying with

and these binomials are computed one by one with $$$O(1)$$$ time for recomputing the next one (with some care to wrap around zero, though). You use

`Q.inv(m)`

in your attached solution, while you could do it without polynomial division. And if this is what theUPDsection is about, then you juggle with formulas that I don't really want to read into, and I hope that I clarified this moment a bit.Huh? I'm not sure I understand. Why divide by $$$(1-x)^s$$$? In my implementation, I find $$$p(x)$$$ and then expand $$$p(x) / (1-x)^n$$$ to find first $$$2n$$$ values of $$$f(k)$$$, rather than the first $$$n$$$. Yes, this particular part could be done in a more efficient way as you described, but it's not what I'm doing in the UPD section, the UPD section is about computing $$$x^s \bmod (x-1)^{n+1}$$$ in $$$O(n)$$$.

Sorry, yes, I meant divide by $$$(1 - x)^n$$$, which is multiplying by $$$\sum\binom{n+i-1}{n-1}x^i$$$, and then taking coefficients from $$$s$$$ to $$$s + m - 1$$$; but this is the same as multiplying with the fps above, but starting with $$$(s-m+1)$$$-th coefficient, and then taking some coefficients from the result. Anyway, it can be done without the polynomial division, and what is happening is you multiply with $$$(1-x)^{-n}$$$ with the first $$$s-m$$$ coefficients dropped.

Ohh, I get it now. Yeah, that makes a lot of sense, thanks!

Hi