给定 (n) 个点,求 (f(x))
由拉格朗日插值法得
[ f(x) = sum_{i = 0}^{n} y_i prod_{i
ot = j} frac{x - x_j}{x_i - x_j}
]
(code :)
for(int i=1;i<=n;++i)
{
ll p=1;
for(int j=1;j<=n;++j)
if(i!=j)
p*=x[i]-x[j];
p=qp(p,mod-2);
for(int j=1;j<=n;++j)
if(i!=j)
p*=k-x[j];
p*=y[i],ans+=p;
}