101 Hack 45 : D. Polynomial Division

ここら辺まではどうにか。
https://www.hackerrank.com/contests/101hack45/challenges/polynomial-division

問題

整数A,Bと整数列C[i]が与えられる。
以下のクエリを順次処理せよ。

• C[i]を1箇所値を変更する。
• 区間[L,R]が与えられる。多項式が1次式でmod pにおいて割り切れるか判定せよ。(p=10^9+7)

解法

P(x)がQ(x)で割り切れるとすると、Q(-b/a)=0よりP(-b/a)も0となるはずである。
あとはBIT等での区間和を取り、mod pにおいて0になるか判定すればよい。

int N,Q;
ll A,B;
ll C[101010];
ll mo=1000000007;
ll V;
ll P[101010];

ll modpow(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;
}

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>Q;
	
	V = (mo-B) * modpow(A) % mo;
	P[0]=1;
	
	FOR(i,N) {
		cin>>C[i];
		bt.add(i+1,C[i]*P[i]%mo);
		P[i+1]=P[i]*V%mo;
	}
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			bt.add(x+1,(mo-(C[x]*P[x]%mo))%mo);
			C[x]=y;
			bt.add(x+1,C[x]*P[x]%mo);
		}
		else {
			if(B==0) {
				if(C[x]%mo==0) {
					cout<<"Yes"<<endl;
				}
				else {
					cout<<"No"<<endl;
				}
			}
			else {
				ll v=bt(y+1)-bt(x);
				if(v%mo==0) {
					cout<<"Yes"<<endl;
				}
				else {
					cout<<"No"<<endl;
				}
			}
		}
	}
	
	
}

まとめ

多項式系の問題は大体P(x)=0を利用する気がするな。