这个算法的用途是，给出 \(n\) 个点，第\(i\)个点为\((x_i,y_i)\)，它可以找出一个 \(n-1\) 次的多项式\(f(x)\)，以便求出\(x\)值为其他情况。
当然也是可以用来整活的，可以构造一些奇奇怪怪的多项式坑人。
首先这个多项式存在是显然的，然后我们求它的方式是一个构造。
我们考虑跟中国剩余定理一个思路，对于\(x_i\)，我们考虑其他的项都消成 \(0\),只有一项为\(y_i\)，就构造出来了。
那么，我们不难想象出一个函数\(f_i(x)\)来处理\(x_i\)的影响：
\[f_i(x)=y_i\prod_{i\not=j}\frac {x-x_j}{x_i-x_j} \]对于其他的\(x_j\)，这一项一定可以消成 \(0\),而对于\(x=x_i\)，则式子刚好为\(y_i\)，也就符合了条件。
于是我们构造出：
\[f(x)=\sum_{i=1}^nf_i(x) \]我们就可以求解了，时间复杂度为\(O(n^2)\)，核心实现如下。
for(int i=1;i<=n;i++)
{
cnt1=1,cnt2=1;
for(int j=1;j<=n;j++)
{
if(i==j)continue;
cnt1=cnt1*(k-x[j])%mod;
cnt2=cnt2*(x[i]-x[j])%mod;
}
ans=(ans+y[i]*cnt1%mod*ksm(cnt2,mod-2)%mod+mod)%mod;
}