Similar Polynomials
Contest: Codeforces Round 869 (Div. 1)
Difficulty rating: 2400
Tags: combinatorics, math

A polynomial $$$A(x)$$$ of degree $$$d$$$ is an expression of the form $$$A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d$$$, where $$$a_i$$$ are integers, and $$$a_d \neq 0$$$. Two polynomials $$$A(x)$$$ and $$$B(x)$$$ are called similar if there is an integer $$$s$$$ such that for any integer $$$x$$$ it holds that

$$$$$$ B(x) \equiv A(x+s) \pmod{10^9+7}. $$$$$$

For two similar polynomials $$$A(x)$$$ and $$$B(x)$$$ of degree $$$d$$$, you're given their values in the points $$$x=0,1,\dots, d$$$ modulo $$$10^9+7$$$.

Find a value $$$s$$$ such that $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$ for all integers $$$x$$$.

Input format:
The first line contains a single integer $$$d$$$ ($$$1 \le d \le 2\,500\,000$$$).

The second line contains $$$d+1$$$ integers $$$A(0), A(1), \ldots, A(d)$$$ ($$$0 \le A(i) < 10^9+7$$$) — the values of the polynomial $$$A(x)$$$.

The third line contains $$$d+1$$$ integers $$$B(0), B(1), \ldots, B(d)$$$ ($$$0 \le B(i) < 10^9+7$$$) — the values of the polynomial $$$B(x)$$$.

It is guaranteed that $$$A(x)$$$ and $$$B(x)$$$ are similar and that the leading coefficients (i.e., the coefficients in front of $$$x^d$$$) of $$$A(x)$$$ and $$$B(x)$$$ are not divisible by $$$10^9+7$$$.

Output format:
Print a single integer $$$s$$$ ($$$0 \leq s < 10^9+7$$$) such that $$$B(x) \equiv A(x+s) \pmod{10^9+7}$$$ for all integers $$$x$$$.

If there are multiple solutions, print any.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$A(x) \equiv x-1 \pmod{10^9+7}$$$ and $$$B(x)\equiv x+2 \pmod{10^9+7}$$$. They're similar because $$$$$$B(x) \equiv A(x+3) \pmod{10^9+7}.$$$$$$

In the second example, $$$A(x) \equiv (x+1)^2 \pmod{10^9+7}$$$ and $$$B(x) \equiv (x+10)^2 \pmod{10^9+7}$$$, hence $$$$$$B(x) \equiv A(x+9) \pmod{10^9+7}.$$$$$$

Example input:
1
1000000006 0
2 3

Example output:
3

Example input:
2
1 4 9
100 121 144

Example output:
9

Editorial:
Not that if polynomials are equivalent, they must have the same leading coefficient $$$k$$$.
Let $$$A(x) = \dots + a x^{d-1} + k x^d$$$ and $$$B(x) = \dots + b x^{d-1} + k x^d$$$. Then
$$$$$$ B(x-s) = \dots + (b-k s d)x^{d-1} + x^d. $$$$$$
So, if $$$A(x)$$$ and $$$B(x)$$$ are equivalent, then $$$A(x) \equiv B(x-s)$$$, where $$$a = b-k s d$$$, or $$$s = \frac{b-a}{kd}$$$.
General remark. On a more intuitive level, you can perceive $$$s$$$ as the value by which you should shift the argument of $$$A(x)$$$, so that the sums of roots of $$$A(x)$$$ and $$$B(x)$$$ coincide, as the coefficient near $$$x^{d-1}$$$ is just the negated sum of roots of the polynomials.
Lagrange interpolation approach. Generally, if $$$f(x_0)=y_0, \dots, f(x_d) = y_d$$$, it is possible to represent $$$f(x)$$$ as
$$$$$$ f(x) = \sum\limits_{i=0}^d y_i \prod\limits_{j \neq i} \frac{x - x_j}{x_i - x_j}. $$$$$$
From this, it is possible to find the coefficients near $$$x^d$$$ and $$$x^{d-1}$$$, that is a sum of corresponding coefficients in each individual summand. Altogether it sums up as
$$$$$$ [x^{d}]f(x) = \sum\limits_{i=0}^d y_i \prod\limits_{j \neq i} \frac{1}{x_i - x_j} = \sum\limits_{i=0}^d y_i \prod\limits_{j \neq i} \frac{1}{i-j} = \sum\limits_{i=0}^d y_i \frac{(-1)^{d-i}}{i! (d-i)!} $$$$$$
Let's denote $$$c_i = \frac{(-1)^{d-i}}{i! (d-i)!}$$$, then it simplifies a bit as
$$$$$$ [x^d] f(x) = \sum\limits_{i=0}^d y_i c_i, $$$$$$
and for the coefficient near $$$d-1$$$ we should note that $$$[x^{d-1}] (x-x_1) \dots (x-x_d) = -(x_1 + \dots + x_d)$$$, thus
$$$$$$ [x^{d-1}]f(x) = -\sum\limits_{i=0}^d y_i c_i \sum\limits_{j \neq i} j = -\sum\limits_{i=0}^d y_i c_i \left(\frac{d(d+1)}{2} - i\right). $$$$$$
Knowing the coefficients near $$$x^d$$$ and $$$x^{d-1}$$$ for both $$$A(x)$$$ and $$$B(x)$$$, it is easy to find $$$a=[x^{d-1}]A(x)$$$, $$$b=[x^{d-1}]B(x)$$$ and $$$k = [x^d] A(x) = [x^d] B(x)$$$, which in turn allow us to compute $$$s$$$ with the formula above.
Finite differences approach. You can consider adjacent differences in values $$$\Delta A(i) = A(i) - A(i+1)$$$. The result $$$\Delta A(i)$$$ is a polynomial in $$$i$$$ that has a degree $$$d-1$$$. Taking the differences $$$d-1$$$ times, we get the values of $$$\Delta^{d-1} A(x)$$$ and $$$\Delta^{d-1} B(x)$$$ in $$$x=\{0, 1\}$$$. On the other hand, $$$\Delta^{d-1} B(x) = \Delta^{d-1} A(x+s)$$$, so you still need to find $$$s$$$, but $$$\Delta^{d-1} A(x)$$$ and $$$\Delta^{d-1} B(x)$$$ are the polynomials of degree $$$1$$$, which makes the whole problem trivial.
Note: To compute $$$\Delta^{d-1} A(0)$$$ and $$$\Delta^{d-1} A(1)$$$ in $$$O(d)$$$, one can use the binomial formula:
$$$$$$ \Delta^k A(x) = \sum\limits_{i=0}^k (-1)^i \binom{k}{i} A(x+i). $$$$$$
Indeed, if we denote by $$$S$$$ an operator such that $$$S A(x) = A(x+1)$$$, then
$$$$$$ \Delta^k A(x)= (I-S)^k A(x)= \sum\limits_{i=0}^k (-1)^i \binom{k}{i} S^i A(x) = \sum\limits_{i=0}^k (-1)^i \binom{k}{i} A(x+i). $$$$$$