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

yukicoderのおかげで解けました。
http://arc033.contest.atcoder.jp/tasks/arc033_4

問題

N次多項式P(x)がある。各項の係数は正整数である。
P(0)～P(N)のN+1個の値が与えられているとき、P(T)を求めよ。

解法

部分点解法

P(x)のi次の係数をB[i]とする。
既知のP(x)の値から以下の式が立てられる。
1*B[0] + 0*B[1] + ... + 0^j*B[j] + ... 0^N*B[N] = P(0)
1*B[0] + 1*B[1] + ... + 1^j*B[j] + ... 1^N*B[N] = P(1)
1*B[0] + 2*B[1] + ... + 2^j*B[j] + ... 2^N*B[N] = P(2)
...
1*B[0] + N*B[1] + ... + N^j*B[j] + ... N^N*B[N] = P(N)

上記(N+1)個の式をガウスの掃出し法で解くと、係数B[i]がすべて求まるので、P(T)が計算できる。

解法

ラグランジュ補間を用いる。
ラグランジュ補間 - Wikipedia

N次式で(N+1)個の値がわかっているので、ラグランジュ補間で完全に式を求めることができる。
今回判明しているP(x)はx=0～Nなので、求めるP(T)はで表現できる。
なのでこのL(x)を高速に求めることを考える。

分子はなので、先に積の値を求めておけば、xごとに(T-x)の逆数を掛けるだけで求められる。
分母は-1～-(N-x)と1～xの積なので、事前に階乗を求めておけばを求めておけばよい。
結局、いずれも前処理をしておけばL(x)は1個O(logT)(T-xの逆数を求める分)で求められる。

int N;
ll A[201000],P[201000];
ll T;
ll mo=1000000007;
ll kai[201000];

ll rev(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	N++;
	kai[0]=1;
	FOR(i,N) {
		cin>>A[i];
		kai[i+1]=kai[i]*(i+1)%mo;
	}
	cin>>T;
	if(T<N) return _P("%lld\n",A[T]);
	
	ll a=1;
	FOR(i,N) a=a*(T+mo-i)%mo;
	
	ll ret=0;
	FOR(i,N) {
		ll b=kai[i]*kai[N-1-i]%mo;
		ll rev2=T-i;
		if(rev2<0) rev2+=mo;
		
		if((N-1-i)%2) b=(mo-b)%mo;
		ret += A[i]*a%mo*rev(rev2)%mo*rev(b)%mo;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

練習の成果もあったもんだ。