XOR After Range Multiplication Queries I
Problem
You are given an array nums of length n and a list of queries [l, r, k, v]. For each query, start at idx = l and while idx ≤ r set nums[idx] = (nums[idx] · v) mod (109+7) then advance idx += k. After all queries, return the bitwise XOR of every element in nums.
nums = [1,1,1], queries = [[0,2,1,4]]4[1,1,1] → [4,4,4]. Then 4 ^ 4 ^ 4 = 4.def xorAfterQueries(nums, queries):
MOD = 10**9 + 7
for l, r, k, v in queries: # apply each query in order
idx = l
while idx <= r: # touch every k-th index in [l, r]
nums[idx] = (nums[idx] * v) % MOD
idx += k
result = 0
for x in nums: # XOR-fold the whole array
result ^= x
return resultfunction xorAfterQueries(nums, queries) {
const MOD = 1000000007n;
for (const [l, r, k, v] of queries) { // apply each query in order
for (let idx = l; idx <= r; idx += k) // touch every k-th index in [l, r]
nums[idx] = Number((BigInt(nums[idx]) * BigInt(v)) % MOD);
}
let result = 0;
for (const x of nums) result ^= x; // XOR-fold the whole array
return result;
}int xorAfterQueries(int[] nums, int[][] queries) {
final long MOD = 1_000_000_007L;
for (int[] q : queries) { // apply each query in order
int l = q[0], r = q[1], k = q[2], v = q[3];
for (int idx = l; idx <= r; idx += k) // every k-th index in [l, r]
nums[idx] = (int) ((long) nums[idx] * v % MOD);
}
int result = 0;
for (int x : nums) result ^= x; // XOR-fold the whole array
return result;
}int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
const long long MOD = 1000000007LL;
for (auto& q : queries) { // apply each query in order
int l = q[0], r = q[1], k = q[2], v = q[3];
for (int idx = l; idx <= r; idx += k) // every k-th index in [l, r]
nums[idx] = (int)((long long)nums[idx] * v % MOD);
}
int result = 0;
for (int x : nums) result ^= x; // XOR-fold the whole array
return result;
}Explanation
With n and q both at most 103, a straightforward simulation is fast enough — we simply do exactly what the problem describes, then fold the array.
For each query [l, r, k, v] we walk a cursor idx from l, jumping by k each time, as long as idx ≤ r. Every visited element is multiplied by v and reduced modulo 109+7. Because nums[i] can be up to 109 and v up to 105, the product overflows 32-bit integers — so we compute it in 64-bit (or with BigInt in JavaScript) before taking the modulo.
After all queries are applied, we XOR every element together. XOR is associative and commutative, so the order of folding does not matter; a single left-to-right pass gives the answer.
One subtle point: the values are reduced mod 109+7 before the XOR. The XOR is taken on these reduced residues, not on the true mathematical products, which is exactly what the statement asks for.
Example: nums = [2,3,1,5,4]. Query [1,4,2,3] hits indices 1 and 3, giving [2,9,1,15,4]. Query [0,2,1,2] hits 0,1,2, giving [4,18,2,15,4]. Then 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31.