e358 - Xor 運算(困難)

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個集合的所有非空子集的 XOR 運算結果之和，並將結果模 1000000007 輸出。

解題思路

這題的核心思想是利用 XOR 運算的性質和組合數學。對於集合中的每個元素，它會在所有包含該元素的子集中出現。考慮集合中的第 i 個元素 a[i]，它會參與 2^(n-1) 個子集的 XOR 運算。由於 XOR 運算具有自反性（a XOR a = 0），因此對於每個位元，每個元素對結果的貢獻是 1 或 0。

程式碼中，bc[i] 記錄了所有元素在第 i 位上為 1 的數量。然後，對於每個位元 i，如果 bc[i] 大於 0，則該位元對最終結果的貢獻是 2^(n-1) * 2^i。由於需要計算模 1000000007 的結果，因此需要使用模運算來避免溢位。

程式碼首先計算每個元素的二進位表示，並統計每個位元上 1 的數量。然後，計算 2^(n-1) mod 1000000007 的值。最後，遍歷每個位元，如果該位元上存在 1，則將對應的貢獻加到結果中，並進行模運算。

複雜度分析

• 時間複雜度: O(n * log(max(a[i])) + 50) 其中 n 是集合的大小，max(a[i]) 是集合中最大元素的數值。log(max(a[i])) 是計算每個元素二進位表示所需的迭代次數。50 是二進位表示的最大位數。
• 空間複雜度: O(50) 主要用於儲存 bc 陣列，其大小為 50。

程式碼

#include <iostream>
#define mod 1000000007
using namespace std;
long long bc[105],n,a[100005];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		long long ans=0,k=1;
		for(int i=0;i<=50;++i){
			bc[i]=0;
		}
		for(int i=0;i<n;++i){
			cin >> a[i];
			int it=0;
			while(a[i]){
				if(a[i]%2){
					bc[it]=1;
				}
				++it;
				a[i]/=2;
			}
		}
		for(int i=0;i<50;++i){
			bc[i]*=(n-1);
		}
		for(int i=1;i<n;++i,k*=2){
			k%=mod;
		}
		for(int i=0,j=1;i<50;++i,j*=2){
			j%=mod;
			if(bc[i]){
				ans+=(j*k)%mod;
				ans%=mod;
			}
		}
		cout << ans << "\n"; 
	}
}