Submission #682153

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll mod = 1000000007;

ll modpow(ll x, ll y, ll mod){
    if(y == 0) return 1;
    ll t = modpow(x, y/2, mod);
    return y%2 == 0 ? t*t%mod : t*t%mod*x%mod;
}

ll modinv(ll x, ll mod){
    return modpow(x, mod-2, mod);
}

ll lagrangeInterpolation(const vector<ll> &x, const vector<ll> &fx, ll t){
    auto it = find(x.begin(), x.end(), t);
    if(it != x.end()) return fx[it - x.begin()];

    int n = x.size() - 1;

    ll nume = 1;
    for(int m = 0; m <= n; ++m){
        nume *= (t-x[m]+mod) % mod;
        nume %= mod;
    }

    ll res = 0;
    for(int k = 0; k <= n; k++){
        ll e = 1;
        for(int m = 0; m <= n; m++){
            if(m != k){
                e *= (x[k]-x[m]+mod) % mod;
                e %= mod;
            }
        }
        ll r = nume;
        r *= modinv((t-x[k]+mod) % mod, mod);
        r %= mod;
        r *= modinv(e, mod);
        r %= mod;
        res += fx[k] * r % mod;
    }
    return res % mod;
}

int main(){
    int n;
    while(cin >> n){
        vector<ll> t(n+1), ft(n+1);
        for(int i = 0; i <= n; ++i){
            t[i] = i;
            cin >> ft[i];
        }
        ll x;
        cin >> x;
        cout << lagrangeInterpolation(t,ft,x) << endl;
    }
    
}

Submission Info

Judge Result