传送门
题意：求给定集合所有子集元素异或和的求和。
a n s = ∑ s i ⊂ S x o r a i , a i ∈ s i ans=\sum\limits_{s_i\subset S}xor\ a_i,a_i\in s_i ans=si⊂S∑xor ai,ai∈si
思路：考虑每个位上的贡献次数。
设对于集合 S S S，当前位上为 1 1 1的个数为 x x x，显然我们需要选出奇数个 1 1 1才能使该位异或为 1 1 1，其他为 0 0 0的数可选可不选，方案数为： 2 n − x 2^{n-x} 2n−x，显然对于 x x x个1，选出奇数个1和偶数个 1 1 1方案是一样的，因为对于 x x x为奇数, ∣ ( 0 , 2 , … , x − 1 ) ∣ = ∣ ( 1 , 3 , … , x ) ∣ |(0,2,\dots,x-1)|=|(1,3,\dots,x)| ∣(0,2,…,x−1)∣=∣(1,3,…,x)∣.
偶数同理。
所以选出奇数个方案数为 2 x − 1 2^{x-1} 2x−1.
所以对于第 k k k位的贡献是： 2 k × 2 n − x × 2 x − 1 = 2 k × 2 n − 1 2^k\times 2^{n-x}\times 2^{x-1}=2^k\times 2^{n-1} 2k×2n−x×2x−1=2k×2n−1.
需要注意的是当 x = 0 x=0 x=0时是不可能产生贡献的，所以我们只需要将集合 S S S中所有数进行按位或运算，再乘上 2 n − 1 2^{n-1} 2n−1即可。
时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=998244353; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second inline void read(int &x){ x=0;int w=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();} for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15); x*=w; } ll ksm(ll a,ll n){ ll ans=1; while(n){ if(n&1) ans=ans*a%mod; a=a*a%mod; n>>=1; } return ans; } int main(){ int t; read(t); while(t--){ int n; read(n); int ans=0; for(reg int i=1;i<=n;i++){ int x; read(x); ans=ans|x; } ans=1LL*ans*ksm(2,n-1)%mod; printf("%d\n",ans); } return 0; }