AtCoder ARC D: 見たことのない多項式

ガウス・ジョルダンの消去法などを知っていればO(n^3)で部分点40(/100)、ラグランジュ補間を知っていればO(n^2)で部分点80(/100)をとれる。

ラグランジュ補間を工夫する。

ラグランジュ補間

一般に多項式P(x)についてi!=jのときx[i]!=x[j]ならば

P(x) = Σ[i=0...n]( P(x[i]) * f[i](x)/f[i](x[i]) )

が成り立つ。

ただし、

f[i](x)

= (Π[j=0..n](x-x[j])) / (x-x[i])

= (x-0)*(x-1)*...*(1)*(-1)*...*(x-n)

とする。

この問題は特殊でx[i]の値が0<=x[i]<=nで与えられていると考えればいい。

よってx[i]をiと置き換えて

P(x) = Σ[i=0...n]( P(i) * f[i](x)/f[i](i) )

ただし

f[i](x)

= (Π[j=0..n](x-j)) / (x-i)

= (x-0)*(x-1)*...*(1)*(-1)*...*(x-n)

となる。

とりあえず、自明だが厄介なケースを取り除いておく。

T<=Nとする。このときP(T)は入力として与えられているので、それを出力するだけ。

なので、以下はT>Nを仮定する。

f[i](T)とf[i](i)がすべてのiについて求まればよい。

f[i](T) = (Π[j=0...n](T-j)) / (T-i)

である。

T>NよりT-j>0が成り立つ。

S=Π[j=0...n](T-j)

として総乗を事前に計算しておけば

f[i](T) = S/(T-i)

のようにO(log(mod))でf[i](T)を求めることができる。

次に、f[i](i)について考えてみる。

f[0](0)をO(N)で求めておく。

f[i](i)からf[i+1](i+1)を計算したい。

f[i](i)

= (i-0)*(i-1)*(i-2)*...*1*(-1)*...*(i-(n-1))*(i-n)

f[i](i+1)

= ( (i+1)-0)*( (i+1)-1)*...*1*(-1)*...*( (i+1)-(n-1))*( (i+1)-n)

f[i](i)とf[i](i+1)の共通点を見てみると、n値の積になっていて、0を除くすべての要素が連続して存在する。

よって1*(-1)から両端にどう延びていくかだけが違いになるが、

前者は左にiまで右にi-nまで、後者は左にi+1まで右にi+1-nまでとなっている。

ここから

f[i](i+1) = f[i]*(i+1) / (i-n)

となる。

これにより、O(log(mod) )でf[i](i+1)を求まる。

以上から、全体で

O(nlog(mod) )

で間に合う。