CF1817C Similar Polynomials

一个次数为 $d$ 的多项式 $A(x)$ 表示为 $A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d$，其中 $a_i$ 是整数，且 $a_d \neq 0$。如果存在一个整数 $s$，使得对于任意整数 $x$，都有 $$ B(x) \equiv A(x+s) \pmod{10^9+7} $$ 则称两个多项式 $A(x)$ 和 $B(x)$ 是相似的。 对于两个次数为 $d$ 的相似多项式 $A(x)$ 和 $B(x)$，给定它们在 $x=0,1,\dots,d$ 处的值（模 $10^9+7$）。 请你找到一个整数 $s$，使得对于所有整数 $x$，都有 $B(x) \equiv A(x+s) \pmod{10^9+7}$。

第一行包含一个整数 $d$（$1 \le d \le 2\,500\,000$）。 第二行包含 $d+1$ 个整数 $A(0), A(1), \ldots, A(d)$（$0 \le A(i) < 10^9+7$），表示多项式 $A(x)$ 在 $x=0,1,\ldots,d$ 处的值。 第三行包含 $d+1$ 个整数 $B(0), B(1), \ldots, B(d)$（$0 \le B(i) < 10^9+7$），表示多项式 $B(x)$ 在 $x=0,1,\ldots,d$ 处的值。 保证 $A(x)$ 和 $B(x)$ 是相似的，且 $A(x)$ 和 $B(x)$ 的首项系数（即 $x^d$ 的系数）都不被 $10^9+7$ 整除。

输出一个整数 $s$（$0 \leq s < 10^9+7$），使得对于所有整数 $x$，都有 $B(x) \equiv A(x+s) \pmod{10^9+7}$。 如果有多个解，输出任意一个即可。

**说明** 在第一个样例中，$A(x) \equiv x-1 \pmod{10^9+7}$，$B(x)\equiv x+2 \pmod{10^9+7}$。它们是相似的，因为 $$ B(x) \equiv A(x+3) \pmod{10^9+7}。 $$ 在第二个样例中，$A(x) \equiv (x+1)^2 \pmod{10^9+7}$，$B(x) \equiv (x+10)^2 \pmod{10^9+7}$，因此 $$ B(x) \equiv A(x+9) \pmod{10^9+7}。 $$ 由 ChatGPT 4.1 翻译