====== 拉格朗日插值法 ======

===== 作用 =====

如果发现某个数学题，答案有可能是多项式的结构的话

然后又恰好打出了表

不如直接插值。也省的推公式了（其实是推不出来

===== Code =====

<code cpp>

int lagrange(int *X, int *Y, ll n, ll k) {
    ll res = 0, l;
    for(int i = 0;i < n; ++i) {
        l = 1;
        for(int j = 0;j < n; ++j) {
            if(i == j) continue;
            l = l * Sub(k, X[j]) % mod;
            l = l * Get_Inv(Sub(X[i], X[j])) % mod;
        }
        res = (res + l * Y[i] % mod) % mod;
    }
    return res;
}


</code>

===== 题目 =====

[[https://atcoder.jp/contests/aising2020/tasks/aising2020_f|Alsing Programming Contest 2020 F]]