library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/lagrange_interpolation.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "math/lagrange_interpolation.hpp"
using mint = atcoder::modint998244353;
mint eval(const std::vector<mint>& coef, mint c) {
    mint r = 0;
    for (int i = int(coef.size()) - 1; i >= 0; i--) r = r * c + coef[i];
    return r;
}
int main() {
    std::mt19937 rng(665);
    for (int it = 0; it < 500; it++) {
        int deg = rng() % 8;
        std::vector<mint> coef(deg + 1);
        for (auto& a : coef) a = rng();
        int n = deg + 1 + rng() % 3;  // extra points are fine
        std::vector<mint> y(n);
        for (int i = 0; i < n; i++) y[i] = eval(coef, i);
        for (int t = 0; t < 5; t++) {
            mint c = rng();
            assert(lagrange_interpolation(y, c) == eval(coef, c));
        }
        for (int i = 0; i < n; i++) assert(lagrange_interpolation(y, mint(i)) == y[i]);
        assert(lagrange_interpolation(y, mint(n)) == eval(coef, n));
        // arbitrary distinct points
        std::set<unsigned> used;
        std::vector<mint> xs, ys;
        while (int(xs.size()) < n) {
            unsigned v = rng();
            if (!used.insert(v).second) continue;
            xs.push_back(v);
            ys.push_back(eval(coef, v));
        }
        for (int t = 0; t < 5; t++) {
            mint c = rng();
            assert(lagrange_interpolation(xs, ys, c) == eval(coef, c));
        }
        for (int i = 0; i < n; i++) assert(lagrange_interpolation(xs, ys, xs[i]) == ys[i]);
    }
    {
        // n = 1: constant
        std::vector<mint> y{7};
        assert(lagrange_interpolation(y, mint(123456789)) == 7);
        assert(lagrange_interpolation(std::vector<mint>{5}, y, mint(3)) == 7);
    }
    {
        // sum of i^k, k = 3: n^2 (n+1)^2 / 4, with 1e5 points for timing
        int k = 3;
        std::vector<mint> y(k + 2);
        for (int i = 1; i <= k + 1; i++) y[i] = y[i - 1] + mint(i).pow(k);
        long long n = 1000000000000000LL;
        mint expect = mint(n) * mint(n) * mint(n + 1) * mint(n + 1) / 4;
        assert(lagrange_interpolation(y, mint(n)) == expect);
        std::vector<mint> big(200000);
        for (int i = 0; i < 200000; i++) big[i] = rng();
        lagrange_interpolation(big, mint(1000000));
    }
    std::cout << "Hello World" << std::endl;
}
#line 1 "test/unit/lagrange_interpolation.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#line 4 "math/lagrange_interpolation.hpp"

#line 4 "math/combinatorics.hpp"
template <typename mint>
struct combinatorics {
    static mint fact(int n) {
        ensure(n);
        return facts[n];
    }
    static mint fact_inv(int n) {
        ensure(n);
        return ifacts[n];
    }
    static mint inv(int n) {
        assert(1 <= n);
        ensure(n);
        return ifacts[n] * facts[n - 1];
    }
    static mint C(int n, int k) {
        if (n < 0 || n < k || k < 0) return 0;
        return fact(n) * fact_inv(n - k) * fact_inv(k);
    }
    static mint P(int n, int k) {
        if (n < 0 || n < k || k < 0) return 0;
        return fact(n) * fact_inv(n - k);
    }
    static mint H(int n, int k) {
        if (n < 0 || k < 0) return 0;
        if (k == 0) return 1;
        return C(n + k - 1, k);
    }
    static void ensure(int n) {
        assert(n < mint::mod());
        int sz = facts.size();
        if (sz > n) return;
        if (n < sz << 1) n = std::min(mint::mod() - 1, sz << 1);
        facts.resize(n + 1);
        ifacts.resize(n + 1);
        for (int i = sz; i <= n; i++) facts[i] = facts[i - 1] * i;
        ifacts[n] = facts[n].inv();
        for (int i = n; i >= sz; i--) ifacts[i - 1] = ifacts[i] * i;
    }

private:
    static inline std::vector<mint> facts{1};
    static inline std::vector<mint> ifacts{1};
};
#line 6 "math/lagrange_interpolation.hpp"
template <class mint> mint lagrange_interpolation(const std::vector<mint>& y, mint c) {
    int n = int(y.size());
    assert(n >= 1);
    long long cv = c.val();
    if (cv < n) return y[cv];
    std::vector<mint> pre(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] * (c - i);
    for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] * (c - i);
    using comb = combinatorics<mint>;
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint t = y[i] * pre[i] * suf[i + 1] * comb::fact_inv(i) * comb::fact_inv(n - 1 - i);
        ret += (n - 1 - i) & 1 ? -t : t;
    }
    return ret;
}
template <class mint>
mint lagrange_interpolation(const std::vector<mint>& x, const std::vector<mint>& y, mint c) {
    int n = int(x.size());
    assert(n >= 1 && int(y.size()) == n);
    mint ret = 0;
    for (int i = 0; i < n; i++) {
        mint num = 1, den = 1;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            assert(x[i] != x[j]);
            num *= c - x[j];
            den *= x[i] - x[j];
        }
        ret += y[i] * num / den;
    }
    return ret;
}
#line 10 "test/unit/lagrange_interpolation.test.cpp"
using mint = atcoder::modint998244353;
mint eval(const std::vector<mint>& coef, mint c) {
    mint r = 0;
    for (int i = int(coef.size()) - 1; i >= 0; i--) r = r * c + coef[i];
    return r;
}
int main() {
    std::mt19937 rng(665);
    for (int it = 0; it < 500; it++) {
        int deg = rng() % 8;
        std::vector<mint> coef(deg + 1);
        for (auto& a : coef) a = rng();
        int n = deg + 1 + rng() % 3;  // extra points are fine
        std::vector<mint> y(n);
        for (int i = 0; i < n; i++) y[i] = eval(coef, i);
        for (int t = 0; t < 5; t++) {
            mint c = rng();
            assert(lagrange_interpolation(y, c) == eval(coef, c));
        }
        for (int i = 0; i < n; i++) assert(lagrange_interpolation(y, mint(i)) == y[i]);
        assert(lagrange_interpolation(y, mint(n)) == eval(coef, n));
        // arbitrary distinct points
        std::set<unsigned> used;
        std::vector<mint> xs, ys;
        while (int(xs.size()) < n) {
            unsigned v = rng();
            if (!used.insert(v).second) continue;
            xs.push_back(v);
            ys.push_back(eval(coef, v));
        }
        for (int t = 0; t < 5; t++) {
            mint c = rng();
            assert(lagrange_interpolation(xs, ys, c) == eval(coef, c));
        }
        for (int i = 0; i < n; i++) assert(lagrange_interpolation(xs, ys, xs[i]) == ys[i]);
    }
    {
        // n = 1: constant
        std::vector<mint> y{7};
        assert(lagrange_interpolation(y, mint(123456789)) == 7);
        assert(lagrange_interpolation(std::vector<mint>{5}, y, mint(3)) == 7);
    }
    {
        // sum of i^k, k = 3: n^2 (n+1)^2 / 4, with 1e5 points for timing
        int k = 3;
        std::vector<mint> y(k + 2);
        for (int i = 1; i <= k + 1; i++) y[i] = y[i - 1] + mint(i).pow(k);
        long long n = 1000000000000000LL;
        mint expect = mint(n) * mint(n) * mint(n + 1) * mint(n + 1) / 4;
        assert(lagrange_interpolation(y, mint(n)) == expect);
        std::vector<mint> big(200000);
        for (int i = 0; i < 200000; i++) big[i] = rng();
        lagrange_interpolation(big, mint(1000000));
    }
    std::cout << "Hello World" << std::endl;
}
Back to top page