题目描述
现在 Cirno 手上有着 \(T\) 天的作业，每天的作业可以用一个二元组 \(( n, V )\) 表示，其中 \(n\) 表示集合的大小， \(V\) 表示大小为 \(n\) 的集合. 现在，Cirno 需要求出的是 \(V\) 的所有子集的异或和的和，答案对 \(998\,244\,353\) 取模。
形式化地:
\[ans \equiv \sum_{S \subset V} \mathop{\oplus}\limits_{ p \in S } p \pmod {998\,244\,353}
\]
数据范围
- Subtask 1（17pts）：$ T, n \le 8 $；
- Subtask 2（22pts）：$ T, n \le 100 $；
- Subtask 3（61pts）：$ T, n \le 3\times10^6 $。
对于 \(100\%\) 的数据，$ \sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$。
思路：
显然这种位运算类型的题目肯定得想到拆位。
假设我们枚举到了第 \(k\) 位，然后 \(n\) 个数中，有 \(x\) 个数的第 \(k\) 位为 \(1\)，有 \(n-x\) 个数的第 \(k\) 位为 \(0\)。
所以要使得当前这一位有贡献，就需要使得选的 \(1\) 的个数为奇数。所以贡献为 \((\sum\limits_{i=1}^{\frac{x+1}{2}}\binom{x}{i}) \times 2^{n-x}\)
然后我们发现这个式子其实就是 \(\binom{x}{1}+\binom{x}{3}+\binom{x}{5}+\cdots =2^{x-1}\)
所以这一位的贡献就应该是 \(2^k\times 2^{x-1}\times 2^{n-x}=2^k\times 2^{n-1}\)
所以我们只需要求出 \((a_1|a_2|a_3|\cdots |a_n)\times 2^{n-1}\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e6+5;
const int mod=998244353;
int T;
int n,a[maxn];
int qp(int x,int k){
int res=1;
while(k){
if(k&1)res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
signed main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int res=0;
for(int i=1;i<=n;i++)res|=a[i];
res=res*qp(2,n-1)%mod;
cout<<res<<endl;
}
return 0;
}
后记：
与这道题类似的还有 P5127 子异和