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

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