C++ – Lagrange

洛谷P4781

题解公式

inline int FastPow(int x, int y) {
    if (y == 1)
        return x;
    if (!y)
        return 1;
    int tmp = FastPow(x, y >> 1) % mod;
    return tmp * tmp % mod * (y & 1 ? x : 1) % mod;
}
inline void Lagrange() {
    go(i, 1, n, 1) {
        up = down = 1;
        go(j, 1, n, 1)
            if (i ^ j) {
                (up *= k - x[j]) %= mod;
                (down *= x[i] - x[j]) %= mod;
            }
        tmp = up * FastPow(down, mod - 2) % mod;
        (ans += y[i] * tmp % mod) %= mod;
    }

    cout << (ans % mod + mod) % mod;
}
signed main() {
    cin >> n >> k;
    go(i, 1, n, 1)
        cin >> x[i] >> y[i];
    Lagrange();
    return 0;
}