AtCoder ABC #137 : F - Polynomial Construction

以前はARCの最終問題のテクだったのになぁ。
https://atcoder.jp/contests/abc137/tasks/abc137_f

問題

素数Pがある。
(P-1)次多項式f(x)に対し、0≦x＜Pにおける、f(x)の値がmod Pで与えられる。
f(x)の係数を求めよ。

解法

(P-1)次式の値がP個わかっているのでラグランジュ補間すればよい。
ラグランジュ補間では多項式の乗算がたくさん出てきて、毎回律儀に乗算するとO(P^3)かかってしまう。
そこで(x-0)(x-1)...(x-(p-1))を求めておいて、適宜(x-i)で割るようにすればよい。

int P;
int A[3030];
ll from[3030],to[3030],B[3030];
ll mo;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	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>>P;
	mo=P;
	
	FOR(i,P) cin>>A[i];
	
	from[0]=1;
	FOR(i,P) {
		ZERO(to);
		FOR(j,3000) to[j+1]=from[j];
		FOR(j,3000) to[j]=(to[j]+P-i*from[j]%P)%P;
		swap(from,to);
	}
	
	
	for(i=0;i<P;i++) if(A[i]) {
		ll Q=1;
		for(j=0;j<P;j++) if(j!=i) Q=Q*(i-j)%mo;
		Q=modpow((Q%mo+mo)%mo);
		
		memmove(to,from,sizeof(from));
		for(j=3000;j>=1;j--) {
			(B[j-1]+=to[j]*Q)%=mo;
			to[j-1]=(to[j-1]+to[j]*i)%mo;
		}
		
	}
	FOR(i,P) cout<<B[i]%P<<" ";
	
}

まとめ

なぜか「P個の項を持つ多項式だから(P+1)個値が無いと」と勘違いしてタイムロスした…。