给你(n)个点：((x_1,y_1),(x_2,y_2),ldots,(x_n,y_n))，求经过这(n)个点的(n-1)次多项式(L(x))
直接高斯消元是(O(n^3))的。
[L(x)=sum_{i=1}^ny_iprod_{j=1,j
eq i}^nfrac{x-x_j}{x_i-x_j}=sum_{i=1}^ny_ifrac{x-x_1}{x_i-x_1}cdotsfrac{x-x_{i-1}}{x_i-x_{i-1}}frac{x-x_{i+1}}{x_i-x_{i+1}}cdotsfrac{x-x_n}{x_i-x_n}
]
设(A(x)=prod_{i=1}^n(x-x_i),B_i(x)=frac{A(x)}{x-x_i},C_i(x)=frac{B_i(x)}{B_i(x_i)})
可以看出
[C_i(x)=frac{x-x_1}{x_i-x_1}cdotsfrac{x-x_{i-1}}{x_i-x_{i-1}}frac{x-x_{i+1}}{x_i-x_{i+1}}cdotsfrac{x-x_n}{x_i-x_n}=egin{cases} 1~~~~(x=x_i)\0~~~~(x=x_j,j
eq i)end{cases}
]
因为当(x=x_i)时每一项的分子都等于分母，当(x=x_j(j eq i))时有一项的分子为(0)。
那么
[L(x)=sum_{i=1}^n y_iC_i(x)
]
这样就可以(O(n^2))算出来了。
代码
(t)个点，插出(t-1)次多项式。
void solve()
{
memset(c,0,sizeof c);
c[0]=1;
memset(ans,0,sizeof ans);
for(i=1;i<=t;i++)
for(j=t;j>=0;j--)
{
(c[j+1]+=c[j])%=p;
(c[j]=-c[j]*x[i])%=p;
}
for(i=1;i<=t;i++)
{
memcpy(d,c,sizeof d);
memset(b,0,sizeof b);
for(j=t;j>=0;j--)
{
b[j]=d[j+1];
d[j]=(d[j]+d[j+1]*x[i])%p;
d[j+1]=0;
}
ll s=0,px=1;
for(j=0;j<=t;j++)
{
s=(s+px*b[j])%p;
px=px*x[i]%p;
}
s=fp(s,p-2)*y[i]%p;
for(j=0;j<=t;j++)
b[j]=b[j]*s%p;
for(j=0;j<=t;j++)
ans[j]=(ans[j]+b[j])%p;
}
}
(n)个点，求(f(m))
void solve()
{
ll ans=0;
for(i=1;i<=n;i++)
{
ll s1=1,s2=1;
for(j=1;j<=n;j++)
if(j!=i)
{
s1=(s1*(m-x[j]))%p;
s2=(s2*(x[i]-x[j]))%p;
}
ans=(ans+y[i]*s1%p*fp(s2,p-2)%p)%p;
}
}