Div.1 C 拉格朗日差值，赛时开香槟。
题目大意
给定 \(d\) 次两个多项式 \(A(x),B(x)\)。求 \(s\)，使得 \(B(x)\equiv A(x+s) \pmod {10^9+7}\) ，保证 \(s\) 存在。
给出多项式的形式为给出 \(x=0,1,\cdots,d\) 模 \(10^9+7\) 的值。
\(d\le 2.5 \times 10^7\)。
题目解析
考虑 \(A(x)\equiv B(x-s) \pmod {10^9+7}\)，展开 \(B(x-s)\)。
发现 \(A(x)\) 和 \(B(x)\) 最高位系数相同（记位 \(k\)），并且只要知道第二高位 \(k_1,k_2\)，那么就有
\(k_1\equiv k_2-2 s k_1\pmod {10^9+7}\)。
所以关键在于求这三个数字。
考虑拉格朗日插值（考虑 \(x_i=i\)，这里直接带入）
\[f(x)=\sum_{i=0}^{d}y_i\prod_{j=1,j\not=i}^{n}\dfrac{x-j}{i-j}
\]
最高项系数为
\[\sum\limits_{i=0}^d\dfrac{y_i}{(-1)^{d-i} i! (d-i)!}
\]
第二高项系数为
\[-\sum\limits_{i=0}^d \dfrac{y_i }{ (-1)^{d-i} i! (d-i)!} \dfrac{d(d+1)}{2}
\]
预处理 \(i!\) 逆元即可，\(\Theta(n)\)。
int n; ll a[maxn],b[maxn],fact[maxn],inv[maxn],k,k1,k2;
ll fpow(ll x,ll y){
ll tmp=x,res=1;
while(y){
if(y&1) res=res*tmp%MOD;
y>>=1; tmp=tmp*tmp%MOD;
} return res;
}
ll getk(int d,ll *p){
ll ans=0; int i;
for(i=0;i<=d;i++){
ll t=p[i]*inv[i]%MOD*inv[d-i]%MOD; if((d-i)&1) t=MOD-t;
ans=(ans+t)%MOD;
} return ans;
}
ll getk2(int d,ll *p){
ll ans=0; int i;
for(i=0;i<=d;i++){
ll t=(1ll*d*(d+1)/2-i)%MOD*p[i]%MOD*inv[i]%MOD*inv[d-i]%MOD; if((d-i)&1) t=MOD-t;
ans=(ans+t)%MOD;
} return MOD-ans;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
n=read(); int i; for(i=0;i<=n;i++) a[i]=read(); for(i=0;i<=n;i++) b[i]=read();
fact[0]=1; for(i=1;i<=n;i++) fact[i]=fact[i-1]*i%MOD;
inv[n]=fpow(fact[n],MOD-2); for(i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%MOD;
k=getk(n,a); k1=getk2(n,a); k2=getk2(n,b);
print((k2-k1+MOD)%MOD*fpow(k*n%MOD,MOD-2)%MOD);
return 0;
}