LeetCode Weekly Contest 463 : 3655. XOR After Range Multiplication Queries II

これ難易度8なのか。
https://leetcode.com/problems/xor-after-range-multiplication-queries-ii/description/

問題

N要素の整数列numと、クエリが複数与えられる。
クエリをすべて適用した後のnumを答えよ。

各クエリは4値L,R,K,Vで構成される。
各クエリに対し、num[L],num[L+K],...num[L+nK]...,num[R]にそれぞれVを掛け、10^9+7で割った余りを取れ。

解法

Kの大小で平方分割する。

• K≦√Nの場合
  • K=1～√Nそれぞれにおいて、K個おきの累積積を取っておく。そうすれば1クエリO(1)で処理出来、最後にO(N√N)でnumに反映する。
• K＞√Nの場合
  • 愚直にnum[L]....にVを掛ける。これは1クエリO(√N)で済む。

const int DI=200;
ll dp[DI+2][101010];
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;
}


class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
		int i,j;
		int N=nums.size();
		FOR(i,DI+2) {
			FOR(j,N) dp[i][j]=1;
		}
		FOR(j,N) dp[0][j]=nums[j];
		FORR(q,queries) {
			int L=q[0],R=q[1]+1,K=q[2],V=q[3];
			if(K>DI) {
				while(L<R) {
					(dp[0][L]*=V)%=mo;
					L+=K;
				}
			}
			else {
				(dp[K][L]*=V)%=mo;
				R=(R-L+K-1)/K*K+L;
				(dp[K][R]*=modpow(V))%=mo;
			}
		}
		
		for(i=1;i<=DI;i++) {
			FOR(j,N) {
				(dp[0][j]*=dp[i][j])%=mo;
				(dp[i][j+i]*=dp[i][j])%=mo;
			}
		}
		ll ret=0;
		FOR(i,N) ret^=dp[0][i];
		return ret;
		
		
        
    }
};

まとめ

やはりLeetCodeは他のコンテストサイトと難易度付けが異なるね。