因為擴散的步伐（傳染的方向）是由展開時的 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）**使用了完全一樣的數學邏輯來分配實體記憶體。
class Solution {
public:
long long maxSubarraySum(vector< int>& nums, int k) {
const int n = nums.size();
vector< long long> kSum(k, 0);
long long maxSum = numeric_limits< long long>::min(), prefixSum = 0;
for (int i = 0; i < k - 1; ++i) {
prefixSum += nums[i];
kSum[i] = prefixSum;
}
for (int i = k - 1; i < n; ++i) {
prefixSum += nums[i];
int r = i % k;
maxSum = max(maxSum, prefixSum - kSum[r]);
kSum[r] = min(kSum[r], prefixSum);
}
return maxSum;
}
};
寫 Python3 是這樣：
class Solution:
def maxSubarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
kSum = [0] * k
prefixSum = 0
maxSum = float("-inf")
for i in range(k - 1):
prefixSum += nums[i]
kSum[i] = prefixSum
for i in range(k - 1, n):
prefixSum += nums[i]
r = i % k
maxSum = max(maxSum, prefixSum - kSum[r])
kSum[r] = min(kSum[r], prefixSum)
return maxSum
寫 Go 是這樣，這邊要注意即便是使用 math.MinInt64 還是要用 int64() 明確轉型，不然預設會用 int 然後就會跟後面的 int64 衝突。
func maxSubarraySum(nums []int, k int) int64 {
n := len(nums)
kSum := make([]int64, k)
prefixSum, maxSum := int64(0), int64(math.MinInt64)
for i := range n {
prefixSum += int64(nums[i])
if i < k-1 {
kSum[i] = prefixSum
continue
}
r := i % k
maxSum = max(maxSum, prefixSum-kSum[r])
kSum[r] = min(kSum[r], prefixSum)
}
return maxSum
}
寫 Rust 是這樣，沒什麼特別要注意的地方，反正寫錯時編譯器會提醒你該如何修正。 :-P
impl Solution {
pub fn max_subarray_sum(nums: Vec< i32>, k: i32) -> i64 {
let k = k as usize;
let n = nums.len();
let mut kSum = vec![0i64; k];
let mut prefixSum = 0i64;
let mut maxSum = i64::MIN;
for i in 0..(k-1) {
prefixSum += nums[i] as i64;
kSum[i] = prefixSum;
}
for i in (k-1)..n {
prefixSum += nums[i] as i64;
let r = i % k;
maxSum = maxSum.max(prefixSum - kSum[r]);
kSum[r] = kSum[r].min(prefixSum);
}
maxSum
}
}
class Solution {
public:
int lengthOfLIS(vector< int>& nums) {
vector< int> arr;
arr.reserve(nums.size());
for (auto& num : nums) {
auto ptr = ranges::lower_bound(arr.begin(), arr.end(), num);
if (ptr == arr.end()) {
arr.push_back(num);
} else {
*ptr = num;
}
}
return arr.size();
}
};
然後是 Python 的 bisect.bisect_left()
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
arr = []
for num in nums:
i = bisect.bisect_left(arr, num)
if i == len(arr):
arr.append(num)
else:
arr[i] = num
return len(arr)
然後是 Go 的 sort.Search()
func lengthOfLIS(nums []int) int {
arr := make([]int, 0, len(nums))
for _, num := range nums {
idx := sort.Search(len(arr), func(i int) bool {
return arr[i] >= num
})
if idx == len(arr) {
arr = append(arr, num)
} else {
arr[idx] = num
}
}
return len(arr)
}
最後是 Rust 的 binary_search
impl Solution {
pub fn length_of_lis(nums: Vec< i32>) -> i32 {
let mut arr = Vec::with_capacity(nums.len());
for num in nums {
let i = match arr.binary_search(&num) {
Ok(index) => index,
Err(index) => index,
};
if i == arr.len() {
arr.push(num);
} else {
arr[i] = num;
}
}
arr.len() as i32
}
}
class Solution {
public:
int minimumOneBitOperations(int n) {
if (n == 0)
return 0;
int k = 32 - __builtin_clz(n);
int ans = 0;
bitset<30> arr(n);
int sign = 1;
for (int i = k; i > 0; --i) {
if (arr[i - 1]) {
ans += sign * ((1 << i) - 1);
sign *= -1;
}
}
return ans;
}
};
簡化後的第二個版本
class Solution {
public:
int minimumOneBitOperations(int n) {
if (n == 0)
return 0;
int k = 32 - __builtin_clz(n);
int ans = 0;
int sign = 1;
for (int i = k; i > 0; --i) {
if (n & (1 << (i - 1))) {
ans += sign * ((1 << i) - 1);
sign *= -1;
}
}
return ans;
}
};
再進一步簡化後的第三個版本
class Solution {
public:
int minimumOneBitOperations(int n) {
if (n == 0)
return 0;
int ans = 0;
int sign = 1;
while (n) {
int k = 32 - __builtin_clz(n);
ans += sign * ((1 << k) - 1);
sign *= -1;
n ^= (1 << (k-1));
}
return ans;
}
};
class Solution {
public:
int countValidSelections(vector< int>& nums) {
int ans = 0, prev = 0, post = accumulate(nums.begin(), nums.end(), 0);
for (auto num : nums) {
if (num == 0) {
if (prev == post)
ans += 2;
else if (abs(prev - post) == 1)
++ans;
} else {
post -= num;
prev += num;
}
}
return ans;
}
};
Python3 就用 sum()
class Solution:
def countValidSelections(self, nums: List[int]) -> int:
ans, prev, post = 0, 0, sum(nums)
for num in nums:
if num == 0:
if prev == post:
ans += 2
elif abs(prev - post) == 1:
ans += 1
else:
prev += num
post -= num
return ans
Go 加總要自己來，abs() 也要自己刻，不過發現可以利用 slices.Values() 在 range 上面，這樣就不用多寫一個 _ 底線，像是 for _, num := range nums 這樣，不過多寫 slices.Values 也不一定好到哪裡去。
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
func countValidSelections(nums []int) int {
ans, prev, post := 0, 0, 0
for num := range slices.Values(nums) {
post += num
}
for num := range slices.Values(nums) {
if num == 0 {
if prev == post {
ans += 2
} else if abs(prev-post) == 1 {
ans += 1
}
} else {
prev += num
post -= num
}
}
return ans
}
impl Solution {
pub fn count_valid_selections(nums: Vec<i32>) -> i32 {
let (mut ans, mut prev, mut post): (i32, i32, i32) = (0, 0, nums.iter().sum());
for num in nums {
if num == 0 {
if prev == post {
ans += 2;
} else if (prev-post).abs() == 1 {
ans += 1;
}
} else {
prev += num;
post -= num;
}
}
ans
}
}
$ echo $PATH
/home/user/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin
$ pbuilder-questing create
W: /root/.pbuilderrc does not exist
I: Distribution is questing.
I: Current time: Tue Oct 14 06:55:39 UTC 2025
I: pbuilder-time-stamp: 1760424939
I: Building the build environment
I: running debootstrap
/usr/sbin/debootstrap
...
I: creating base tarball [/home/user/pbuilder/questing-base.tgz]
...
接下來我們可以抓 Debian libchewing source package 來試試看
$ pull-debian-source libchewing
Found libchewing 0.10.3-1 in sid
...
Downloading libchewing_0.10.3.orig.tar.xz from deb.debian.org (1.571 MiB)
[=====================================================>]100%
Downloading libchewing_0.10.3-1.debian.tar.xz from deb.debian.org (0.008 MiB)
[=====================================================>]100%
$ pbuilder-questing build libchewing_0.10.3-1.dsc
W: /root/.pbuilderrc does not exist
I: pbuilder: network access will be disabled during build
I: Current time: Tue Oct 14 07:02:09 UTC 2025
I: pbuilder-time-stamp: 1760425329
I: Building the build Environment
I: extracting base tarball [/home/user/pbuilder/questing-base.tgz]
...
dpkg-deb: building package 'libchewing3-data' in '../libchewing3-data_0.10.3-1_all.deb'.
dpkg-deb: building package 'libchewing3-dev' in '../libchewing3-dev_0.10.3-1_amd64.deb'.
dpkg-deb: building package 'libchewing3' in '../libchewing3_0.10.3-1_amd64.deb'.
dpkg-deb: building package 'chewing-tools' in '../chewing-tools_0.10.3-1_amd64.deb'.
...
$ cd ~/pbuilder/ && ls *chewing*
chewing-tools_0.10.3-1_amd64.deb libchewing_0.10.3-1_amd64.buildinfo libchewing_0.10.3-1.debian.tar.xz libchewing_0.10.3-1_source.changes libchewing3_0.10.3-1_amd64.deb libchewing3-dbgsym_0.10.3-1_amd64.ddeb
chewing-tools-dbgsym_0.10.3-1_amd64.ddeb libchewing_0.10.3-1_amd64.changes libchewing_0.10.3-1.dsc libchewing_0.10.3.orig.tar.xz libchewing3-data_0.10.3-1_all.deb libchewing3-dev_0.10.3-1_amd64.deb
看起來目前的 libchewing 0.10.3-1 in sid 可以在 Ubuntu 25.10 正常編譯沒有問題。
class Solution:
def removeAnagrams(self, words: List[str]) -> List[str]:
return [next(g) for _, g in groupby(words, sorted)]
Go 原本是用轉換成排序後的字串當鍵值
func removeAnagrams(words []string) []string {
var prev string
ans := make([]string, 0, len(words))
for _, word := range words {
runes := []rune(word)
slices.Sort(runes)
key := string(runes)
if key != prev {
ans = append(ans, word)
prev = key
}
}
return ans
}
Go 後來發現用 bytes.Equal 直接比較排序後的 []byte 也不錯
func removeAnagrams(words []string) []string {
prev := []byte{}
ans := make([]string, 0, len(words))
for _, word := range words {
key := []byte(word)
slices.Sort(key)
if !bytes.Equal(key, prev) {
ans = append(ans, word)
prev = key
}
}
return ans
}
Rust 用轉換排序後的字串當鍵值效率沒那麼好，可能是因為要顧及 UTF-8 的轉換問題
impl Solution {
pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
let mut prev = "".to_string();
let mut ans = Vec::with_capacity(words.len());
for word in words {
let copy = word.clone();
let mut chars = word.chars().collect::< Vec< char>>();
chars.sort_unstable();
let key = chars.into_iter().collect::< String>();
if key != prev {
prev = key;
ans.push(copy);
}
}
ans
}
}
Rust 改用排序後的 Vec< u8> 陣列直接比較就簡單有效多了
impl Solution {
pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
let mut prev: Vec< u8> = Vec::new();
let mut ans = Vec::with_capacity(words.len());
for word in words {
let mut key: Vec< u8> = word.bytes().collect();
key.sort_unstable();
if key != prev {
prev = key;
ans.push(word);
}
}
ans
}
}
Rust 也可以利用 fold 寫出函數式程式設計的風格
impl Solution {
pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
let initial = (Vec::with_capacity(words.len()), Vec::< u8>::new());
let (ans, _) = words.into_iter().fold(initial, |(mut ans, mut prev), word| {
let mut key: Vec< u8> = word.bytes().collect();
key.sort_unstable();
if key != prev {
prev = key;
ans.push(word);
}
(ans, prev)
});
ans
}
}
func maximumTotalDamage(power []int) int64 {
n := 0
slices.Sort(power)
arr := [100000]int{}
count := [100000]int{}
for _, p := range power {
if n == 0 || arr[n-1] != p {
n += 1
arr[n-1] = p
count[n-1] = 1
} else {
count[n-1]++
}
}
j := 0
var mx int64
f := make([]int64, n)
for i := range n {
for i > j && arr[i] > arr[j]+2 {
mx = max(mx, f[j])
j++
}
f[i] = mx + int64(arr[i])*int64(count[i])
}
return slices.Max(f)
}
impl Solution {
pub fn maximum_total_damage(mut power: Vec<i32>) -> i64 {
power.sort_unstable();
let mut arr = [0; 100000];
let mut count = [0; 100000];
let mut n = 0;
for p in power {
if n == 0 || arr[n - 1] != p as usize {
n += 1;
arr[n - 1] = p as usize;
count[n - 1] = 1;
} else {
count[n - 1] += 1;
}
}
let mut f = vec![0i64; n];
let mut j = 0;
let mut mx = 0;
for i in 0..n {
while i > j && arr[i] > arr[j] + 2 {
mx = mx.max(f[j]);
j += 1;
}
f[i] = mx + arr[i] as i64 * count[i] as i64;
}
f.into_iter().max().unwrap()
}
}
