読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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)は P(T) = \sum_x P(x)*L(x)で表現できる。
 \displaystyle L(x)=\frac{(T-0)(T-1)..(T-(x-1))(T-(x+1))...(T-N)}{(x-0)(x-1)..(x-(x-1))(x-(x+1))...(x-N)}なのでこのL(x)を高速に求めることを考える。

分子は \displaystyle  \frac{\prod_{i=0}^N (T-i)}{T-x}なので、先に積の値を求めておけば、xごとに(T-x)の逆数を掛けるだけで求められる。
分母は-1~-(N-x)と1~xの積なので、事前に階乗を求めておけば (N-x)!*x!*(-1)^{N-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;
	
}

まとめ

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

広告を非表示にする