题解【Luogu P6102 谔运算】

\[\texttt{Description}
\]

给出一个长度为 \(n\) 的数列 \(a\)，求 \(\sum\limits_{i=1}\limits^{n}\sum\limits_{j=1}\limits^{n}\sum\limits_{k=1}\limits^{n}\sum\limits_{l=1}\limits^{n}(a_i \ \text{or} \ a_j) \ \text{xor} \ (a_k \ \text{and} \ a_l)\) 。

\[\texttt{Solution}
\]

先考虑下普通的谔运算 \((a \ \text{or} \ b) \ \text{xor} \ (c \ \text{and} \ d)\) 什么时候为真（\(a,b,c,d \in \{ 0,1 \}\)），我们发现 \(a,b,c,d\) 一共有 \(16\) 种取值，其中有 \(10\) 种取值使得式子为真：
\(a = 0, b = 0, c = 1, d = 1\) ；

\(a = 0, b = 1, c = 0, d = 0\) ；

\(a = 0, b = 1, c = 0, d = 1\) ；

\(a = 0, b = 1, c = 1, d = 0\) ；

\(a = 1, b = 0, c = 0, d = 0\) ；

\(a = 1, b = 0, c = 0, d = 1\) ；

\(a = 1, b = 0, c = 1, d = 0\) ；

\(a = 1, b = 1, c = 0, d = 0\) ；

\(a = 1, b = 1, c = 0, d = 1\) ；

\(a = 1, b = 1, c = 1, d = 0\) 。
然后考虑按位分组计算贡献。
详细地说：\((a \ \text{or} \ b) \ \text{xor} \ (c \ \text{and} \ d)\) 得到的数，若第 \(i\) 位为真，则对答案有 \(2^i\) 的贡献。由于谔运算是按位处理的，也就是说我们可以计算出对答案有贡献的数中，有多少个数第 \(i\) 位为真，若将这个量记为 \(c_i\) ，最后答案即为 \(\sum\limits_{i=0}\limits^{31}c_i \times 2^i\) 。
我们记 \(cnt[i,j]\) 表示 \(a\) 中有多少数第 \(i\) 位为 \(j\) ，可以 \(\text{O(32n)}\) 预处理。
然后按位分组计算贡献，根据乘法原理和加法原理，从 \(a\) 中选出 \(4\) 个数进行谔运算，第 \(i\) 位为真的四元组有 \(cnt[i,0] \times cnt[i,0] \times cnt[i,1] \times cnt[i,1] + cnt[i,0] \times cnt[i,1] \times cnt[i,0] \times cnt[i,0] + ......\) ，最后将其乘上 \(2^i\) 计入答案中。
注意到此题的膜数为 \(2^{32}\) ，所以，记得要开 \(\text{unsigned} \ \text{int}\)。
时间复杂度 \(\text{O(32n)}\) 。

\[\texttt{Code}
\]

#include<cstdio>

#include<iostream>

#define RI register int

using namespace std;

namespace IO

{

    static char buf[1<<20],*fs,*ft;

    inline char gc()

    {

        if(fs==ft)

        {

			ft=(fs=buf)+fread(buf,1,1<<20,stdin);

			if(fs==ft)return EOF;

        }

        return *fs++;

    }

    #define gc() getchar()

	inline int read()

	{

		unsigned int x=0,f=1;char s=gc();

		while(s<'0'||s>'9')s=gc();

		while(s>='0'&&s<='9')x=x*10+s-'0',s=gc();

		return x*f;

	}

}using IO::read;

const int N=500100;

int n;

int a[N];

unsigned int cnt[33][2];

unsigned int ans;

int main()

{

	n=read();

	for(RI i=1;i<=n;i++)

		a[i]=read();

	for(RI i=1;i<=n;i++)

		for(RI j=0;j<32;j++)

			cnt[j][(a[i]>>j)&1]++;

	for(RI i=0;i<32;i++)

	{

		unsigned int c=0;

		c+=cnt[i][0]*cnt[i][0]*cnt[i][1]*cnt[i][1];

		c+=cnt[i][0]*cnt[i][1]*cnt[i][0]*cnt[i][0];

		c+=cnt[i][0]*cnt[i][1]*cnt[i][0]*cnt[i][1];

		c+=cnt[i][0]*cnt[i][1]*cnt[i][1]*cnt[i][0];

		c+=cnt[i][1]*cnt[i][0]*cnt[i][0]*cnt[i][0];

		c+=cnt[i][1]*cnt[i][0]*cnt[i][0]*cnt[i][1];

		c+=cnt[i][1]*cnt[i][0]*cnt[i][1]*cnt[i][0];

		c+=cnt[i][1]*cnt[i][1]*cnt[i][0]*cnt[i][0];

		c+=cnt[i][1]*cnt[i][1]*cnt[i][0]*cnt[i][1];

		c+=cnt[i][1]*cnt[i][1]*cnt[i][1]*cnt[i][0];

		ans+=c*(1<<i);

	}

	printf("%u\n",ans);

	return 0;

}

\[\texttt{Thanks} \ \texttt{for} \ \texttt{watching}
\]

巴特西

题解【Luogu P6102 谔运算】

最新文章

热门文章