用Lagrange插值公式求多项式系数。这个实现针对域Fp上的多项式，且p很小（<= 2999）的情形。一般情况下需要注意爆 long long 的问题。来自 ABC137F。

【模板】拉格朗日插值求多项式系数.cpp

// tourist 的逆元模板
template <typename T>
T inverse(T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
        T t = m / a;
        m -= t * a; swap(a, m);
        u -= t * v; swap(u, v);
    }
    assert(m == 1);
    return u; // 注意：u 可能为负数
}
 
// 多项式除法：a / (x - v)
vi poly_div(vi a, int v, int p) {
    int n = SZ(a);
    vi res(n - 1);
    down (i, n - 1, 1) {
        res[i - 1] = a[i];
        a[i - 1] += v * a[i] % p;
        a[i - 1] %= p;
    }
    assert(a[0] == 0);
    return res;
}
 
vi lagrange_interpolation(const vector<pii>& a, int p) {
    int n = SZ(a);
    vi prod(n + 1);
    prod[0] = 1;
    rng (i, 0, n) {
        down(j, i + 1, 1) {
            prod[j] = prod[j - 1] - a[i].first * prod[j] % p;
            if (prod[j] < 0) prod[j] += p;
        }
        prod[0] = prod[0] * -a[i].first % p;
        if (prod[0] < 0) {
            prod[0] += p;
        }
    }
 
    vi res(n);
    rng (i, 0, n) {
        auto tmp = poly_div(prod, a[i].first, p);
        int fm = 1;
        rng (j, 0, n) {
            if (j != i) {
                fm *= (a[i].first - a[j].first + p);
                fm %= p;
            }
        }
        int coeff = inverse(fm, p) * a[i].second % p;
        if (coeff < 0) coeff += p;
        rng (j, 0, n) {
            res[j] += coeff * tmp[j] % p;
        }
    }
    For (x, res) x %= p;
    return res;
}