多項式補間に関して教えてもらったのでまとめておきます。
何らかのN次関数P(x)があったとします。xが小さい場合は簡単に計算できる時、それを利用して大きなxに対しても求めたいです。
連立方程式を解くと各項の係数が求められますが、O(N^3)掛かってしまいます。
それをO(N^2)にする方法の１つとして、ラグランジュ補間があります。
Qi(x) = (x-0)*(x-1)*...*(x-N) / (x-i)
という関数を考えると、N次多項式は必ず、
P(x) = c0*Q0(x) + c1*Q1(x) + ... + cN*QN(x)
という形で書けるそうです。
この関数Qの嬉しい所は、xにiを代入すると、Qi以外は全部0になって除去できる所です。
xにiを代入して考えると、係数ciはP(i)/Qi(i)となっており、簡単に計算できます。
各Qを求めるためにO(N)で、項がN個なので、O(N^2)で答えが求まることになります。
また、ニュートン補間というのもあるらしいです。
こちらは、
Ri(x) = (x-0)*(x-1)*...*(x-(i-1))
という関数を考えて、
P(x) = c0*R0(x) + c1*R1(x) + ... + cN*RN(x)
と書き表そうとします。
係数を0から順番に計算して行くと項iをO(i)で求められます。
ニュートン補間の嬉しい所は、Ri(x)の式にNが含まれていないため、Nが増えた時でもO(N)で係数を更新できる所です。
（ただ、競プロでNが増えるような問題はまず無いと思います。）
両方組んでみたのですが、競プロではラグランジュ補間の方をお勧めします。その理由は、ニュートン補間の方は全ての係数を記録しておかないと次の係数が計算できないからです。（式が少しややこしいというのもあります）
例題はSRM629Div1HardとKUPC2013ドミノの問題でしょうか。
追記 [2015/02/01]：まんまラグランジュ補間を問う問題です。ちょっと考えるとO(N)に落ちるらしい。
