yukicoder : No.1938 Lagrange Sum

しばらく間が空いてしまった。
https://yukicoder.me/problems/no/1938

問題

N個の整数対(X[i],Y[i])が与えられる。
多項式F[i](x)は、i≠jであるjに対しF[i](X[j])=Y[j]を満たすような(N-1)次式とする。
また、F(x)=sum(F[i](x))とする。

正整数Xが指定されるのでF(X)を求めよ。

解法

愚直にラグランジュ補間をN回やっても解けると思われるが、Editorialにある通り下記整形済みの式に代入するだけでも解ける。

int N;
ll V,X[101010],Y[101010];
ll S[101010],T[101010];
const ll mo=998244353;

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>>N>>V;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
	}
	ll SS=0,ST=0,SST=0;
	FOR(i,N) {
		S[i]=1;
		T[i]=1;
		FOR(j,N) if(i!=j) {
			S[i]=S[i]*(V-X[j])%mo;
			T[i]=T[i]*(X[i]-X[j])%mo;
		}
		T[i]=Y[i]*modpow(T[i]%mo+mo)%mo;
		(SS+=S[i])%=mo;
		(ST+=T[i])%=mo;
		(SST+=S[i]*T[i])%=mo;
	}
	
	ll ret=(N*SST-SS*ST)%mo;
	cout<<(ret+mo)%mo<<endl;
	
	
}

まとめ

想定解は、愚直にラグランジュ補間繰り返すのと、ある程度式変形した後代入するのとどっちなんだろうな。