因為擴散的步伐（傳染的方向）是由展開時的 k 決定的，所以：
👉 同一個 diff 陣列在展開時，只能服務一種 k。
這就是為什麼我們要在外層寫一個 for k in range(1, B + 1):，每次輪到一個新的 k，我們就把 diff 陣列清空重置，讓它專心只處理這批步伐為 k 的包裹！
🧩 第四步：將所有拼圖組合起來 (完整程式碼解析)
現在我們擁有了所有武器，來看看完整的高階寫法是如何運作的：
import math
from typing import List
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
MOD = 10**9 + 7
n = len(nums)
# 【策略一：根號分治】計算閾值 B
B = max(1, math.isqrt(n))
# 準備空陣列，用來依照步長 k 分組存放小步伐查詢
grouped_queries = [[] for _ in range(B + 1)]
# 分流查詢
for l, r, k, v in queries:
if v == 1: continue # 小優化：乘數為 1 不改變數字
if k <= B:
# 步伐小，存起來等一下批次處理
grouped_queries[k].append((l, r, v))
else:
# 步伐大，直接暴力更新 (次數保證小於 B)
for i in range(l, r + 1, k):
nums[i] = (nums[i] * v) % MOD
# 【策略二：乘法差分】處理小步伐查詢
diff = [1] * n
for k in range(1, B + 1):
if not grouped_queries[k]: continue
# 每次換新的步長 k，重置差分陣列
for i in range(n): diff[i] = 1
for l, r, v in grouped_queries[k]:
# 1. 區間起點：標記乘上 v
diff[l] = (diff[l] * v) % MOD
# 2. 區間終點外：計算越界的第一個位置
num_steps = (r - l) // k
next_idx = l + (num_steps + 1) * k
if next_idx < n:
# 標記乘上 v 的反元素 (相當於除以 v，用來抵銷)
inv_v = pow(v, -1, MOD)
diff[next_idx] = (diff[next_idx] * inv_v) % MOD
# 3. 前綴積展開：將記號擴散回原陣列
for i in range(n):
if i >= k:
diff[i] = (diff[i] * diff[i - k]) % MOD
if diff[i] != 1:
nums[i] = (nums[i] * diff[i]) % MOD
# 【最終收尾】：計算 XOR 總和
result = 0
for num in nums:
result ^= num
return result
from typing import List
import math
from collections import defaultdict
class Solution:
def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
MOD = 10**9 + 7
n = len(nums)
if n == 0: return 0
# 【策略一：根號分治】
B = int(math.sqrt(n)) + 1
# 只記錄有出現的小步伐查詢
small = defaultdict(list)
# 處理大步伐 (直接暴力做)
for l, r, k, v in queries:
if k >= B:
idx = l
while idx <= r:
nums[idx] = (nums[idx] * v) % MOD
idx += k
else:
small[k].append((l, r, v))
# factors 用來累積所有小步伐造成的最終乘數
factors = [1] * n
# 【策略二：殘差類掃描 (Residue Class Sweep)】
for k, qlist in small.items():
# 依照 l % k 分組記錄事件
events = [[] for _ in range(k)]
for l, r, v in qlist:
res = l % k
step = (r - l) // k
last = l + step * k
# 放入事件：(起點, 乘上 v)
events[res].append((l, v))
# 放入事件：(終點外, 乘上 v 的模逆元抵銷)
end_idx = last + k
if end_idx < n:
inv_v = pow(v, MOD - 2, MOD) # 費馬小定理求模逆元
events[res].append((end_idx, inv_v))
# 針對每個殘差類獨立掃描
for res in range(k):
ev = events[res]
if not ev: continue
ev.sort() # 依照 index 排序事件
cur_multiplier = 1
ptr = 0
m = len(ev)
# 順著步伐 k 跳躍掃描
i = res
while i < n:
# 如果走到事件觸發點，更新目前的乘數
while ptr < m and ev[ptr][0] == i:
cur_multiplier = (cur_multiplier * ev[ptr][1]) % MOD
ptr += 1
factors[i] = (factors[i] * cur_multiplier) % MOD
i += k
# 【最終收尾】統一將累積的乘數寫回 nums，並計算 XOR
ans = 0
for i in range(n):
nums[i] = (nums[i] * factors[i]) % MOD
ans ^= nums[i]
return ans
🌟 同場加映：極速版 C++ 實作
競技程式設計界最受歡迎的 C++ 實作版本。邏輯與上述 Python 極速版完全相同，加上了快速冪 (Binary Exponentiation) 來手動實作模逆元，在 LeetCode 上能達到極低的執行時間與記憶體消耗。
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
long long MOD = 1e9 + 7;
int n = nums.size();
if (n == 0) return 0;
// 【策略一：根號分治】
int B = sqrt(n) + 1;
// 紀錄小步伐查詢
unordered_map<int, vector<vector<int>>> small;
// 處理大步伐
for (const auto& q : queries) {
int l = q[0], r = q[1], k = q[2], v = q[3];
if (v == 1) continue; // 小優化：乘數為 1 不改變數字
if (k >= B) {
int idx = l;
while (idx <= r) {
nums[idx] = (1LL * nums[idx] * v) % MOD;
idx += k;
}
} else {
small[k].push_back({l, r, v});
}
}
// factors 用來累積所有小步伐的乘數
vector<long long> factors(n, 1);
// 快速冪 (用於費馬小定理求模逆元)
auto power = [&](long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
};
// 【策略二：殘差類掃描】
for (const auto& [k, qlist] : small) {
// events[res] 存放 (index, factor) 對
vector<vector<pair<int, long long>>> events(k);
for (const auto& q : qlist) {
int l = q[0], r = q[1];
long long v = q[2];
int res = l % k;
int step = (r - l) / k;
int last = l + step * k;
events[res].push_back({l, v});
int end_idx = last + k;
if (end_idx < n) {
long long inv_v = power(v, MOD - 2);
events[res].push_back({end_idx, inv_v});
}
}
// 獨立掃描每個殘差類
for (int res = 0; res < k; ++res) {
auto& ev = events[res];
if (ev.empty()) continue;
sort(ev.begin(), ev.end());
long long cur_multiplier = 1;
int ptr = 0;
int m = ev.size();
// 順著步伐 k 往前跳
for (int i = res; i < n; i += k) {
while (ptr < m && ev[ptr].first == i) {
cur_multiplier = (cur_multiplier * ev[ptr].second) % MOD;
ptr++;
}
factors[i] = (factors[i] * cur_multiplier) % MOD;
}
}
}
// 統一寫回 nums 並計算 XOR
int ans = 0;
for (int i = 0; i < n; ++i) {
nums[i] = (1LL * nums[i] * factors[i]) % MOD;
ans ^= nums[i];
}
return ans;
}
};
MOD = 10**9 + 7
v = 4
# Python 內建魔法，直接求 4 在模 10^9+7 下的模逆元
inv_v = pow(v, -1, MOD)
# 或是手動利用費馬小定理：v^(MOD-2) % MOD
inv_v_fermat = pow(v, MOD - 2, MOD)
print(inv_v) # 輸出：250000002
C++ 實作
在 C++ 中，我們需要手動實作快速冪函數（Binary Exponentiation）：
#include <iostream>
long long MOD = 1e9 + 7;
// 快速冪實作：計算 (base^exp) % MOD
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
// 如果當前二進位最低位是 1，則乘上當前的 base
if (exp % 2 == 1) {
res = (res * base) % MOD;
}
// base 自我平方 (A^1 -> A^2 -> A^4 -> A^8 ...)
base = (base * base) % MOD;
// 將 exp 右移一位 (等同於 exp /= 2)
exp /= 2;
}
return res;
}
// 求模逆元
long long modInverse(long long n) {
// 根據費馬小定理，逆元為 n^(MOD-2)
return power(n, MOD - 2);
}
int main() {
long long v = 4;
std::cout << "4 的模逆元是: " << modInverse(v) << std::endl;
// 驗證： (4 * 250000002) % 1000000007 == 1
return 0;
}
class Solution {
bool solve(string& ans, int n, int& k) {
if (ans.size() == n) {
return --k == 0; // 找到第 k 個組合時停止
}
for (char c : {'a', 'b', 'c'}) {
if (!ans.empty() && c == ans.back()) continue; // 核心約束
ans.push_back(c);
if (solve(ans, n, k)) return true; // 提早回傳
ans.pop_back(); // 回溯
}
return false;
}
public:
string getHappyString(int n, int k) {
string ans = "";
return solve(ans, n, k) ? ans : "";
}
};
工程思考
這種方法就像是在迷宮中探路。雖然直觀，但當 n 變大時，搜尋空間會呈指數級成長。在系統底層開發中，過深的遞迴會導致 Stack Overflow，這在核心（Kernel）環境中是絕對要避免的。
class Solution {
public:
string getHappyString(int n, int k) {
int m = 1 << (n - 1); // 每個分支的組合數 (2^(n-1))
if (3 * m < k) return ""; // 總數檢查
string ans = "";
k--; // 轉為 0-indexed 處理區間
// 1. 確定首位字元
ans.push_back('a' + k / m);
k %= m;
// 2. 數學跳轉確定後續字元
for (int i = 1; i < n; ++i) {
m >>= 1; // 剩餘組合數減半
char next = 'a' + (k / m);
if (next >= ans.back()) next++; // 巧妙排除重複，維持字典序
ans.push_back(next);
k %= m;
}
return ans;
}
};
深入核心：Linux Kernel 中的精準對應
我們在上述數學解法中使用了兩個核心技巧：「基於 2 的冪次方的空間劃分」與「前置狀態的數學補償」。在 Linux 核心中，這兩個技巧有著極其精準的對應實例。
實例 A：二進位空間劃分 —— 夥伴系統 (Buddy System)
在快樂字串中，我們利用 m = 1 << (n - 1) 來確定區間，並用除法與餘數直接定位分支。
在 Linux 的記憶體管理核心 mm/page_alloc.c 中，著名的**夥伴系統（Buddy Allocator）**使用了完全一樣的數學邏輯來分配實體記憶體。
