2019-02-10 20:46:05

$$f(x)=\sum_{i=1}^n y_i\prod_{j=1,j\not = i}^n \frac{x-x_j}{x_i-x_j}$$

$$=\sum_{i=1}^n \frac{y_i}{\prod_{j=1,j\not = i}^n(x_i-x_j)}*\prod_{j=1,j\not = i}^n(x-x_j)$$

$$f_{l,r}(x)=\sum_{i=l}^r \frac{y_i}{\pi'(x)}*\prod_{j=l,j\not = i}^r(x-x_j)$$

$$=[\prod_{j=mid+1}^r(x-x_j)]*\sum_{i=l}^{mid}\frac{y_i}{\pi'(x)}*[\prod_{j=l,j\not =i}^{mid}(x-x_j)]$$$$+[\prod_{j=l}^{mid}(x-x_j)]*\sum_{i=mid+1}^r\frac{y_i}{\pi'(x)}*[\prod_{j=mid+1,j\not =i}^r(x-x_j)]$$

$$= [\prod_{j=mid+1}^r(x-x_j)]f_{l,mid}(x)+[\prod_{j=l}^{mid}(x-x_j)]f_{mid+1,r}(x)$$


static int fst[MAXN];

void calcf(int*x,int l,int r,int lev)
{
if(l==r){pol[lev][0]=fst[l];return;}
int mid=(l+r)>>1;
calcf(x,l,mid,lev+1);
calc(x,mid+1,r,0,0);//这是分治乘法
mul(pol[lev+1],solv[0][0],pol[lev],mid-l,r-mid);//这是多项式乘法
calcf(x,mid+1,r,lev+1);
calc(x,l,mid,0,0);
mul(pol[lev+1],solv[0][0],Q,r-mid-1,mid-l+1);
}

inline void getfunc(int*x,int*y,int*F,int n)
{
calc(x,1,n,0,0);
Rep(i,0,n)pol[0][i]=solv[0][0][i];
Deriv(pol[0],pol[0],n);//这是求导
getnum(x,fst,1,n,0,n-1);//这是多点求值
Rep(i,1,n)fst[i]=(ll)y[i]*power(fst[i],mod-2)%mod;
calcf(x,1,n,0);//主函数
Rep(i,0,n-1)F[i]=pol[0][i];
}
• star
首页