【洛谷5390】[Cnoi2019] 数学作业（位运算）

点此看题面

大致题意： 给你一个集合，求所有子集异或和之和。

大致思路

首先，我们很容易想到去对二进制下每一位分别讨论。

枚举当前位，并设共有\(x\)个数当前位上为\(1\)，则有\((n-x)\)个数当前位上为\(0\)。

对于\(x=0\)显然无法使这一位为\(1\)，否则当且仅当选取的子集中有奇数个数这一位上为\(1\)，这一位异或之后才会为\(1\)。

又由于这一位为\(0\)的数选与不选毫无影响，因此这一位为\(1\)的方案数为\(x\)个数中选取奇数个数的方案数乘上\(2^{n-x}\)。

则我们主要考虑如何求\(x\)个数中选取奇数个数的方案数。

容易想到去猜测\(x\)个数中选取奇数个数的方案数与选取偶数个数的方案数相同，即皆为\(2^{x-1}\)。

实际上，由二项式定理我们可知：

\[(1-1)^x=\sum_{i=1}^x(-1)^iC_x^i=0
\]

由这个式子就可以推得上面的结论是正确的了。

所以对于任意\(x≠0\)的一位，其方案数即为\(2^{x-1}\cdot2^{n-x}=2^{n-1}\)。

综上，我们得出结论：对于二进制下第\(k\)位，若这一位有\(1\)，则可产生\(2^k\cdot2^{n-1}\)的贡献。

因此将所有数或起来，然后乘上\(2^{n-1}\)就是答案了。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define X 998244353

using namespace std;

int n;

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];

	public:

		I FastIO() {A=B=FI;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

		Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}

		Tp I void writeln(Con Ty& x) {write(x),pc('\n');}

		I void clear() {fwrite(FO,1,C,stdout),C=0;}

}F;

I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂

int main()

{

	RI Tt,i,s,x;F.read(Tt);W(Tt--)

	{

		for(F.read(n),s=0,i=1;i<=n;++i) F.read(x),s|=x;//统计所有数或值

		F.writeln(1LL*s*Qpow(2,n-1)%X);//乘上2的n-1次方

	}return F.clear(),0;

}

巴特西

【洛谷5390】[Cnoi2019] 数学作业（位运算）

大致思路

代码

最新文章

热门文章