🔗 🟢 1863. Sum of All Subset XOR Totals 1372

tags: `Weekly Contest 241` `暴力法(Brute Force)` `回溯(Backtracking)` `位運算(Bit Manipulation)` `狀態壓縮` `數學(Math)`

雖然是 Easy 題，但 $O(n)$ 的解法可不簡單。

題意

一個陣列的 異或總和(XOR Total) 定義為陣列中所有元素按位 XOR 的結果，如果陣列為空，則異或總和為 0 。

給定一個陣列 $nums$ ，請你求出 $nums$ 中每個子集的 異或總和 ，計算並返回這些值相加之和。

限制

$1 \leq nums.length \leq 12$
$1 \leq nums[i] \leq 20$

思路

方法一：暴力法(Brute Force) + 回溯(Backtracking) + 狀態壓縮

暴力枚舉所有子集，計算每個子集的 XOR 和。比較直覺的方法是可以用回溯法來實現，但可以注意到陣列的長度最多只有 $12$ ，而每個元素都只有在或不在子集中兩種狀態，所以可以把每個元素的狀態用二進位表示，這樣就可以用一個長度為 $12$ 的二進位數來表示一個子集，並且將枚舉子集轉換成枚舉數字，這就是狀態壓縮。

直接枚舉 $[0, 2^n)$ 之間的所有數字，對於每個數字，對應的二進位數中的每一位，如果該位是 1，則將對應的元素異或到當前子集的 XOR 和中，最後將當前子集的 XOR 和加到答案中即可。此外，由於空子集的 XOR 和為 0，所以其實可以從 $1$ 開始枚舉。

複雜度分析

時間複雜度： $O(n \cdot 2^n)$ ，枚舉所有子集需要 $O(2^n)$ 的時間，對於每個子集，需要 $O(n)$ 的時間計算 XOR 和。
空間複雜度： $O(1)$ 。

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(1 << n):  # 枚舉所有子集，狀態壓縮
            cur = 0  # 當前子集的 XOR 和
            for j in range(n):
                if i & (1 << j):  # 當前元素是否在子集中
                    cur ^= nums[j]
            ans += cur
        return ans

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < (1 << n); i++) {  // 枚舉所有子集，狀態壓縮
            int cur = 0;                      // 當前子集的 XOR 和
            for (int j = 0; j < n; j++)       // 當前元素是否在子集中
                if (i & (1 << j)) cur ^= nums[j];
            ans += cur;
        }
        return ans;
    }
};

方法二：數學(Math) + 位運算(Bit Manipulation)

由於 XOR 是按位運算，所以可以按位考慮每個子集中該位 $1$ 的個數。

若該子集中該位 $1$ 的個數為奇數，則該位的 XOR 值為 $1$
若該子集中該位 $1$ 的個數為偶數，則該位的 XOR 值為 $0$

接著從元素中該位的值來考慮所有子集中該位的 XOR 和，可以得到以下結論：

若所有元素中的該位皆為 $0$ ，則在所有 $2^n$ 個子集中，該位的 XOR 和皆為 $0$ ，故總貢獻顯然也為 $0$ 。
若至少有一個元素中的該位為 $1$ ，則總共有 $2^{n-1}$ 個子集中該位 $1$ 的個數為奇數、 $2^{n-1}$ 個子集中該位 $1$ 的個數為偶數，也就是說會有 $2^{n-1}$ 個子集合在該位上產生貢獻。

可以透過以下兩種方法證明：

方法一：二項式定理
假設陣列中該位為 $1$ 的元素個數為 $m$ ，則有 $n-m$ 個元素的該位為 $0$ ，故包含 k 個 1 的子集數量為：

$2^{n-m}\binom{m}{k}$

而根據二項式定理：

$(x + 1)^m = \binom{m}{0} + \binom{m}{1} x + \binom{m}{2} x^2 + ... + \binom{m}{m} x^m$

將 $x = -1$ 代入，可以得：

$(1 - 1)^m = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \binom{m}{3} + ... = 0 \tag{1}$

又將 $x = 1$ 代入，可以得：

$(1 + 1)^m = \binom{m}{0} + \binom{m}{1} + \binom{m}{2} + ... + \binom{m}{m} = 2^m \tag{2}$

根據 $(1)$ 和 $(2)$ 可以得出：

$\binom{m}{0} + \binom{m}{2} + \binom{m}{4} + ... = \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + ... = 2^{m-1} \tag{3}$

即包含偶數個 1 和包含奇數個 1 的子集數量相等，皆為 $2^{m-1} \times 2^{n-m} = 2^{n-1}$ 。
方法二：選或不選
假設陣列中至少有一個數該位為 $1$ ，則可以先取出 1 個 1，此時剩下的 $n-1$ 個元素可以形成 $2^{n-1}$ 個子集，考慮這些子集：
- 若該子集中有偶數個 $1$ ，則可以選額外的 $1$ ，此時有奇數個 1
- 若該子集中有奇數個 $1$ ，則可以不選額外的 $1$ ，此時有奇數個 1
也就是說，這 $2^{n-1}$ 個子集都能透過選或不選額外的 1 來得到奇數個 1，故可以得出 $2^{n-1}$ 個子集中該位 1 的個數為奇數。

最後考慮貢獻，若所有元素的第 $i$ 位中至少有一個元素的該位為 $1$ ，則該位對答案的貢獻為 $2^{n-1} \times 2^i$ ，所以只要判斷在所有元素中是否有一個元素的該位為 $1$ ，就能計算對答案的貢獻。可以計算所有元素的 OR 值，最後乘上 $2^{n-1}$ ，也就是左移 $n-1$ 位即可。

複雜度分析

時間複雜度： $O(n)$ ，計算所有元素的 OR 值需要 $O(n)$ 的時間。
空間複雜度： $O(1)$ 。

1
2
3

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x | y, nums) << (len(nums) - 1)

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        return reduce(nums.begin(), nums.end(), 0, bit_or<int>())
               << (nums.size() - 1);
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, backlight, anime style,

1girl, solo, Nahida, Nahida (Genshin Impact), long hair, fair skin, pointed ears, large green eyes, green eyes, white hair, white hair with Dendro-green tips, bangs, symbol-shaped pupils, gradient hair, white dress, sitting on a blanket, straw hat, outdoor, grass, picnic, soft lighting, looking at viewer, serene, peaceful, folding chair, small table with food and drinks, holding a sandwich, a variety of picnic foods including various sandwiches, fruits, and drinks spread on the blanket and small table, creating a vibrant and inviting picnic atmosphere.

The scene depicts Nahida from Genshin Impact, enjoying a serene picnic outdoors. She is sitting gracefully on a colorful blanket, surrounded by an array of delicious sandwiches and fruits. The setting is complete with a folding chair and a small table laden with food and drinks, creating a warm and inviting atmosphere under the soft, natural lighting.