CF1817C Similar Polynomials 题解
jiangtaizhe001
·
·
题解
可能更好的阅读体验
题目传送门
Div.1 C 拉格朗日差值，赛时开香槟。
UPD：有个地方打错了，已经更正。
题目大意
给定 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 的值。
### 题目解析
考虑 $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)!} \left(\dfrac{d(d+1)}{2}-i\right)$$
预处理 $i!$ 逆元即可，$\Theta(n)$。
```cpp
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;
}
```