Codeforces #869 : Div1 C. Similar Polynomials

コードは短いんだよな。
https://codeforces.com/contest/1817/problem/C

問題

d次の多項式2つA,Bが与えられる。
B(x) = A(x+s) (mod 1000000007)となるsが存在するので、解を1つ求めよ。

解法

A(x)のd次の次数をk、(d-1)次の次数をa、B(x)のd次の次数をk'、(d-1)次の次数をbとする。
この時k=k'かつs=(b-a)/kdとなる。
あとはa,b,kを求めればよい。
これはラグランジュ補間の要領で計算できる。

int D;
const ll mo=1000000007;

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;
	
	const int NUM_=2600003;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}

	cin>>D;
	vector<ll> A(D+1),B(D+1);
	FOR(i,D+1) cin>>A[i];
	FOR(i,D+1) cin>>B[i];
	
	ll As=0,Bs=0,K=0;
	FOR(i,D+1) {
		ll yc=factr[i]%mo*factr[D-i]%mo;
		if((D-i)%2) yc=mo-yc;
		(K+=A[i]*yc)%=mo;
		(As-=A[i]*yc%mo*((1LL*D*(D+1)/2)%mo-i))%=mo;
		(Bs-=B[i]*yc%mo*((1LL*D*(D+1)/2)%mo-i))%=mo;
	}
	As=(As%mo+mo)%mo;
	Bs=(Bs%mo+mo)%mo;
	ll ret=(Bs+mo-As)*modpow(K*D)%mo;
	cout<<ret<<endl;
	
}

まとめ

ラグランジュ補間苦手だな…。