Shift of polynomial sampling points

Правка en1, от adamant, 2023-05-01 18:48:47

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

$$$ f_m = a_1 f_{m-1} + \dots + a_{n+1} f_{m-(n+1)}. $$$

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

$$$ g(x) = \sum\limits_{k=0}^\infty f_k x^k $$$

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

$$$ q(x) = 1-\sum\limits_{k=1}^{n+1} a_k x^k, $$$

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

$$$ A(x) = x^{n+1} - \sum\limits_{k=1}^{n+1} a_k x^{(n+1)-k} = x^{n+1} q(x^{-1}), $$$

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

Теги polynomials

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский adamant 2023-05-04 13:35:10 2 Tiny change: 'rac{(-1)^{j-i} f(i)}{' -> 'rac{(-1)^{n-i} f(i)}{'
en14 Английский adamant 2023-05-04 13:32:31 1261 Tiny change: 'e identity\n\n$$\n[x' -> 'e identity for $k \geq 1$:\n\n$$\n[x'
en13 Английский adamant 2023-05-03 23:21:23 4
en12 Английский adamant 2023-05-03 11:50:02 11 doesn't seem true
en11 Английский adamant 2023-05-03 11:35:22 266
en10 Английский adamant 2023-05-03 10:57:51 444
en9 Английский adamant 2023-05-02 13:36:12 2 Tiny change: 'inom{n+k}{k} x^k,\n$$' -> 'inom{n+k}{n} x^k,\n$$'
en8 Английский adamant 2023-05-02 13:32:45 617 Tiny change: ' there is much simp' -> ' there is a much simp'
en7 Английский adamant 2023-05-02 12:58:46 479 Tiny change: 'x)^{n+1}$. Perhaps th' -> 'x)^{n+1}$.\n\nPerhaps th'
en6 Английский adamant 2023-05-02 12:45:27 608 Tiny change: 'that only first $2n$ coeffici' -> 'that only the first $2n+1$ coeffici'
en5 Английский adamant 2023-05-02 12:34:36 620 Tiny change: '] = (-1)^{k-n}\binom{s-' -> '] = (-1)^{n-i}\binom{s-'
en4 Английский adamant 2023-05-02 03:17:34 103
en3 Английский adamant 2023-05-01 21:25:01 13 Tiny change: 's too.\n\n#### G' -> 's too.\n\n[cut]<br>\n\n#### G'
en2 Английский adamant 2023-05-01 20:47:54 1561 Tiny change: 'R(x)$ and $$.' -> 'R(x)$ and then $O(n \log n)$ to find $f_s, \dots, f_{s+n}$.' (published)
en1 Английский adamant 2023-05-01 18:48:47 1739 Initial revision (saved to drafts)