Shift of polynomial sampling points

Hi everyone!

Previously, I had a blog on how, given and a polynomial , to compute coefficients of the polynomial .

Today we do it in values space. Consider the problem Library Judge — Shift of Sampling Points of Polynomial. In this problem, you're given and the values of a polynomial of degree at most and you need to find .

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 be a linear recurrence, such that

Given and , we need to find . The problem generalizes that of finding specific value .

Generally, we can say that are the coefficients near of , where

is the generating function of . On the other hand, , where

and is a polynomial of degree at most . Let

then only has positive powers of if is divisible by . Thus, the coefficients near non-positive powers of will not change if we replace by its remainder modulo . So, we need coefficients near of the product , where . Note that only first coefficients of affect the result, hence the whole problem may be solved in for finding and then to find .

Shift in polynomials

In polynomials, it is possible to implement the solution above in instead of . For this we should note that also form a linear recurrence with a very specific characteristic polynomial . Thus,

can be transformed via substitution into

The identity above allows us to find

from which we can obtain the final result by substituting back

which can then be computed as a regular Taylor shift by of in .

Questions to audience

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