yukicoder : No.1349 Subset Product Queries

ちょっと迷ったけどわかると簡単。
https://yukicoder.me/problems/no/1349

問題

整数列Aと正整数Pが与えられる。
以下のクエリに答えよ。

• 数列中の区間[L,R]と値Kが指定される。A[L]...A[R]の部分集合のうち、積を取ってPで割った余りがKになるものがあるか判定せよ。

解法

A	とPがさほど大きくないので、以下を前処理として求めよう。

f(n,k) := A[m]...A[n]のうち部分集合の積をPで割った余りがkにできるようなmの最大値
f(n-1,*)の結果に対し、A[n]を部分集合に取り入れる/取り入れないケースを考えれば、f(n,k)を求めることができる。

あとは各クエリについて、f(R,K)がL以上かどうかを判定すればよい。

int N,Q,P;
int A[5050];
int L[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>P;
	MINUS(L);
	FOR(i,N) {
		cin>>A[i];
		// take
		L[i][A[i]]=i;
		if(i) {
			FOR(x,P) {
				L[i][x]=max(L[i][x],L[i-1][x]);
				L[i][x*A[i]%P]=max(L[i][x*A[i]%P],L[i-1][x]);
			}
		}
	}
	while(Q--) {
		cin>>x>>y>>r;
		if(L[y-1][r]>=x-1) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

まとめ

割とコードが短い。