Struct nekolib::math::Interpolation

pub struct Interpolation { /* private fields */ }

Lagrange 補間。

与えられた $\langle f(0), f(1), \dots, f(n-1)\rangle$ に対して $\hat{f}(i)=f(i)$ ($i=0,1,\dots,n-1$) なる $n$ 次多項式 $\hat{f}$ を考える。 この $\hat{f}$ に対して $\hat{f}(x)\bmod p$ を返す。

Idea

todo!()

Complexity

前処理に $O(n)$ 時間、$\hat{f}(x)$ を求めるのに $O(n)$ 時間。

Examples

use nekolib::math::Interpolation;

let f = Interpolation::with(vec![0, 1, 3], 998244353);
assert_eq!(f.interpolate(0), 0);
assert_eq!(f.interpolate(3), 6);
assert_eq!(f.interpolate(4), 10);
assert_eq!(f.interpolate(100000000), 722404071);

See also

• https://rsk0315.hatenablog.com/entry/2019/04/25/141012

Implementations

impl Interpolation

pub fn with(first: Vec<u64>, modulo: u64) -> Self

pub fn interpolate(&self, x: u64) -> u64