水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 033:D - 見たことのない多項式

問題

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 した&他人のコードを見た.

f:id:babcs2035:20180918191738p:plain