Polynomial Construction [AtCoder Beginner Contest 137 F]

https://atcoder.jp/contests/abc137/tasks/abc137_f

前提知識

• ラグランジュ補間

解説

https://atcoder.jp/contests/abc137/submissions/6896149

ラグランジュ補間ができるのでやる。
N個の頂点からO(N²)でN-1次元以下の多項式を復元できる。
https://mathtrain.jp/hokan
ここや
http://kmjp.hatenablog.jp/entry/2019/08/10/0930
kmjpさんの実装を参考にして、実装した。
多項式の前計算が大変なのだが、頑張る。
x=0,1,2,3,...となっていると高速計算できたような気がするが、一旦どんな点であっても大丈夫なやつをライブラリ化した。
O(P²)

int P, A[3030];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P;
    rep(i, 0, P) cin >> A[i];

    vector<pair<int, int>> ps;
    rep(i, 0, P) ps.push_back({ i, A[i] });

    auto ans = LagrangePolynomialGetCoefficient(ps, P);

    rep(i, 0, P) {
        if (i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
}