从拉格朗日插值法还原多项式

这里有份实现该功能的代码

int Mul(const LL &x,const LL &y) {return x * y % mo;} int Add(const int &x,const int &y) {return (x + y) % mo;} int Dec(const int &x,const int &y) {return (x - y + mo) % mo;} void Work(int now) { int *t1 = B,*t2 = C; for (int i = 0; i <= 2 * n; i++) f[i] = Calc(i); for (int i = 0; i <= 2 * n; i++) { for (int j = 0; j <= 2 * n; j++) B[j] = C[j] = 0; int tmp = f[i]; t1[0] = 1; for (int j = 0; j <= 2 * n; j++) { if (i == j) continue; tmp = Mul(tmp,Inv[i - j]); for (int k = 1; k <= 2 * n; k++) t2[k] = t1[k - 1]; t2[0] = 0; for (int k = 0; k <= 2 * n; k++) t2[k] = Dec(t2[k],Mul(t1[k],j)); swap(t1,t2); } for (int j = 0; j <= 2 * n; j++) D[j] = Add(D[j],Mul(tmp,t1[j])); } }