説明

$N$ 次多項式 $f(x)$ があって、$f(0), f(1), \cdots, f(N)$ がわかっているとする。このとき任意の値 $t$ に対して $f(t)$ がラグランジュ補完により復元可能。

計算量

  • $O(N + \log mod)$

実装例

依存ライブラリ Mod-Int Combination

  • lagrange_polynomial($y$, $t$)
template< typename T >
T lagrange_polynomial(const vector< T > &y, int64_t t) {
  int N = y.size() - 1;
  Combination< T > comb(N);
  if(t <= N) return y[t];
  T ret(0);
  vector< T > dp(N + 1, 1), pd(N + 1, 1);
  for(int i = 0; i < N; i++) dp[i + 1] = dp[i] * (t - i);
  for(int i = N; i > 0; i--) pd[i - 1] = pd[i] * (t - i);
  for(int i = 0; i <= N; i++) {
    T tmp = y[i] * dp[i] * pd[i] * comb.rfact(i) * comb.rfact(N - i);
    if((N - i) & 1) ret -= tmp;
    else ret += tmp;
  }
  return ret;
}

検証

AtCoder ARC_033_D - 見たことのない多項式

int main() {
  int N, T;
  cin >> N;
  vector< modint > A(N + 1);
  cin >> A;
  cin >> T;
  cout << lagrange_polynomial(A, T) << endl;
}