ラグランジュ補間
(NumberTheory/ModularArithmetic/lagrange_interpolation.py)

• View this file on GitHub
• Last update: 2022-01-16 22:03:51+09:00

概要

$x$ が相異なる $n + 1$ 個の点 $(x_0, y_0),\ldots,(x_n, y_n)$ 全てに対して $f(x_i) = y_i$ を満たす $n$ 次多項式 $f$ を考える。このときに $f(T)$ の値を求めるアルゴリズム。

使い方

lagrange_interpolation_naive(points: Iterable[[int, int]], T: int, MOD: int) -> int
$N + 1$ 個の点 points を通る $N$ 次多項式 $f$ について、$f(T)$ の値を返す。計算量 $O(N^2)$

lagrange_interpolation(y: Sequence[int], T: int, MOD: int) -> int
$N$ 次多項式 $f$ について $f(0), f(1), \ldots, f(N)$ の値を配列 y として与えたとき 、$f(T)$ の値を返す。計算量 $O(N + \log\mathrm{MOD})$

Verify

問題: ARC003-D 見たことのない多項式
提出: https://atcoder.jp/contests/arc033/submissions/28588350

Code

def lagrange_interpolation_naive(points, T, MOD):
    n = len(points) - 1
    x, y = list(zip(*points))
    res = 0
    for i in range(n + 1):
        numer = 1
        denom = 1
        for j in range(n + 1):
            if i == j:
                continue
            numer *= T - x[j]
            numer %= MOD
            denom *= x[i] - x[j]
            denom %= MOD
        ci = numer * pow(denom, MOD - 2, MOD) % MOD
        res += y[i] * ci
        res %= MOD
    return res


def lagrange_interpolation(y, T, MOD):
    n = len(y) - 1
    T %= MOD
    if 0 <= T <= n:
        return y[T]

    fact = 1
    inv_fact = [1] * (n + 1)
    for val in range(1, n + 1):
        fact = fact * val % MOD
    inv_fact[n] = pow(fact, MOD - 2, MOD)
    for i in reversed(range(1, n + 1)):
        inv_fact[i - 1] = inv_fact[i] * i % MOD

    left = [1] * (n + 1)
    for i in range(n):
        left[i + 1] = (left[i] * (T - i)) % MOD

    r = 1
    res = 0
    for i in reversed(range(n + 1)):
        numer = r * left[i] % MOD
        denom = inv_fact[i] * inv_fact[n - i] % MOD
        ci = numer * denom % MOD
        if (n - i) % 2 == 1:
            ci *= -1
        res = (res + y[i] * ci) % MOD
        r = r * (T - i) % MOD
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page