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),…,f(n) of a polynomial of degree at most n and you need to find f(s),f(s+1),…,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 f0,f1,… be a linear recurrence, such that
Given s and f0,…,fn, we need to find fs,…,fs+n. The problem generalizes that of finding specific value fs.
Generally, we can say that fs,…,fs+n are the coefficients near x0,x−1,…,x−n of xsg(x−1), where
is the generating function of fk. On the other hand, g(x)=p(x)q(x), where
and p(x) is a polynomial of degree at most n. Let
then D(x)g(x−1)=xn+1p(x−1) only has positive powers of x if D(x) is divisible by A(x). Thus, the coefficients near non-positive powers of xsg(x−1) will not change if we replace xs by its remainder modulo A(x). So, we need coefficients near x0,x−1,…,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}. 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
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?