310345: CF1817C. Similar Polynomials
Description
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$.
InputThe 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$.
OutputPrint 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.
ExamplesInput1 1000000006 0 2 3Output
3Input
2 1 4 9 100 121 144Output
9Note
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}.$$
Input
题意翻译
给定两个次数为 $d$ 的多项式 $A, B$ 在 $0, 1, 2, \dots, d$ 处的点值对 $10^9+7$ 取模，保证 $B(x) \equiv A(x+s) \pmod {10^9+7}$。求 $s \bmod 10^9+7$。Output
C. 相似多项式
一个次数为d的多项式A(x)形式为A(x) = a_0 + a_1 x + a_2 x^2 + ... + a_d x^d，其中a_i是整数，并且a_d ≠ 0。如果存在整数s，使得对于任意整数x，都有B(x) ≡ A(x+s) (mod 10^9+7)，那么称多项式A(x)和B(x)相似。给定两个相似的多项式A(x)和B(x)的度d，以及它们在x=0,1,...,d点的值（模10^9+7），找出一个值s，使得对于所有整数x，都有B(x) ≡ A(x+s) (mod 10^9+7)。
输入输出数据格式：
输入：
- 第一行包含一个整数d (1 ≤ d ≤ 2,500,000)。
- 第二行包含d+1个整数A(0), A(1), ..., A(d) (0 ≤ A(i) < 10^9+7) —— 多项式A(x)的值。
- 第三行包含d+1个整数B(0), B(1), ..., B(d) (0 ≤ B(i) < 10^9+7) —— 多项式B(x)的值。
- 保证A(x)和B(x)相似，并且A(x)和B(x)的最高次项系数（即x^d前的系数）不被10^9+7整除。
输出：
- 打印一个整数s (0 ≤ s < 10^9+7)，使得对于所有整数x，都有B(x) ≡ A(x+s) (mod 10^9+7)。
- 如果有多个解，打印任意一个。题目大意： C. 相似多项式 一个次数为d的多项式A(x)形式为A(x) = a_0 + a_1 x + a_2 x^2 + ... + a_d x^d，其中a_i是整数，并且a_d ≠ 0。如果存在整数s，使得对于任意整数x，都有B(x) ≡ A(x+s) (mod 10^9+7)，那么称多项式A(x)和B(x)相似。给定两个相似的多项式A(x)和B(x)的度d，以及它们在x=0,1,...,d点的值（模10^9+7），找出一个值s，使得对于所有整数x，都有B(x) ≡ A(x+s) (mod 10^9+7)。 输入输出数据格式： 输入： - 第一行包含一个整数d (1 ≤ d ≤ 2,500,000)。 - 第二行包含d+1个整数A(0), A(1), ..., A(d) (0 ≤ A(i) < 10^9+7) —— 多项式A(x)的值。 - 第三行包含d+1个整数B(0), B(1), ..., B(d) (0 ≤ B(i) < 10^9+7) —— 多项式B(x)的值。 - 保证A(x)和B(x)相似，并且A(x)和B(x)的最高次项系数（即x^d前的系数）不被10^9+7整除。 输出： - 打印一个整数s (0 ≤ s < 10^9+7)，使得对于所有整数x，都有B(x) ≡ A(x+s) (mod 10^9+7)。 - 如果有多个解，打印任意一个。