3653. XOR After Range Multiplication Queries I

📘 題目敘述

給定一個整數陣列 nums，長度為 n，以及一個二維陣列 queries，其中 queries[i] = [li, ri, ki, vi]。

對於每一筆 query，都要依照以下流程操作：

• 先設 idx = li
• 只要 idx <= ri，就做：
  • nums[idx] = (nums[idx] * vi) % (10^9 + 7)
  • 然後 idx += ki

當所有 query 都處理完之後，請回傳整個 nums 陣列所有元素的 bitwise XOR。

條件限制

• 1 <= n == nums.length <= 10^3
• 1 <= nums[i] <= 10^9
• 1 <= q == queries.length <= 10^3
• queries[i] = [li, ri, ki, vi]
• 0 <= li <= ri < n
• 1 <= ki <= n
• 1 <= vi <= 10^5

🧠 解題思路

我這題的想法就是直接照題目敘述模擬。

因為每筆 query 都明確告訴我要：

• 從哪個位置開始
• 每次跳幾格
• 乘上多少
• 而且要對 10^9 + 7 取模

所以我就直接一筆一筆 query 去做更新。 每次沿著 li, li + ki, li + 2ki, ... 這些位置一路更新到超過 ri 為止。

全部更新完之後，再把整個陣列做一次 XOR，就得到答案。

這題的資料範圍不大，所以直接模擬就可以過。

所有變數

• MOD：題目要求取模的常數 10^9 + 7
• idx：目前這筆 query 正在更新的索引位置
• ans：最後整個陣列做 XOR 的結果

🪜 主要流程步驟

1. 先設定模數常數

因為每次更新都要做：

• 先乘上 vi
• 再對 10^9 + 7 取模

所以我先把這個常數存起來：

const int MOD = 1e9 + 7;

這樣後面寫更新時會比較方便，也比較不容易寫錯。

2. 一筆一筆處理所有 query

我用一個迴圈掃過所有 queries：

for (auto& a : queries) {

每個 a 就是一筆 query，也就是：

• a[0]：li
• a[1]：ri
• a[2]：ki
• a[3]：vi

這樣我後面就可以直接照題目指定的規則更新陣列。

3. 對每筆 query，從 li 開始每次跳 ki 格做更新

進到某一筆 query 之後，我先把：

int idx = a[0];

也就是從 li 開始。

接著只要 idx <= a[1]，就代表目前位置還在這筆 query 的範圍內，所以要更新：

while (idx <= a[1]) {
    nums[idx] = (1LL * nums[idx] * a[3]) % MOD;
    idx += a[2];
}

這段就是完全照題目在做：

• 把 nums[idx] 乘上 vi
• 對 MOD 取模
• 然後把 idx 往後跳 ki 格

這裡我特別寫成：

1LL * nums[idx] * a[3]

是因為乘法結果可能先超過 int 範圍，所以先轉成 long long 比較安全。

4. 全部 query 做完之後，從頭到尾計算 XOR

當所有 query 都處理完之後，nums 就已經是最終狀態了。

所以我接著用 ans 來累積 XOR 值。 一開始先讓：

int ans = nums[0];

然後從第二個元素開始一路 XOR 下去：

for (int i = 1; i < nums.size(); i++) {
    ans = ans ^ nums[i];
}

因為題目要的是整個陣列所有元素的 bitwise XOR，所以這樣掃一次就可以得到最終答案。

5. 回傳最後答案

當整個陣列都 XOR 完之後，ans 裡面就是題目要的結果，直接回傳即可。

⏱️ 複雜度

設 n = nums.length，q = queries.length。

• 時間複雜度：O(qn) 每筆 query 在最壞情況下可能會更新接近整個陣列，最後還要再掃一次陣列做 XOR。
• 空間複雜度：O(1) 除了幾個額外變數之外，沒有另外使用和輸入大小成比例的額外空間。

💻 程式碼實作

class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        const int MOD = 1e9 + 7;
        for (auto& a : queries) {
            int idx = a[0];
            while (idx <= a[1]) {
                nums[idx] = (1LL * nums[idx] * a[3]) % MOD;
                idx += a[2];
            }
        }
        int ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            ans = ans ^ nums[i];
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/xor-after-range-multiplication-queries-i/