AtCoder Regular Contest 033:D - 見たことのない多項式
問題
N 次多項式 P(x) があり,P(0), P(1), ... , P(N) が分かっているとき,P(T) を求める問題.
解法
さっぱり分からないので解説を読んだところ,ラグランジュ補間というものを使うらしいと分かった.これは,P(x) を P(v) * (v の式) で表すことができるもの.それぞれ逆元も用いて求めることができる.O(N log mod).
解答
Submission #3220582 - AtCoder Regular Contest 033
実装が分からず 1 WA した&他人のコードを見た.