题解 P4932 【浏览器】

可爱的__stdcall大佬都说得非常明白了

毕竟是出题人

但是本蒟蒻发现自己的$O(n)$方法好像不太一样...

首先是一个玄学的popcnt统计代码

int BitCount(unsigned int n){
	unsigned int c=0;
	for (c=0;n;++c){//遍历n的最小的1的位置
		n&=(n-1);//将n移到最小的1的位
	}
	return c ;
}

既然需要对所有的边都进行判定，那么按照暴力的想法，需要写一个双重循环去暴力判定
如下伪代码：

for (i,1,n)
	for (j,1,i-1)
    	if ( popcnt(x[i] xor x[j]) is odd)
        ans++

这么暴力一定会被续的

所以就要考虑 $-x[i]-$ 和 $-x[i-1]-$ 对结果的贡献了

考虑若$-a \oplus b-$与$-a \oplus c-$与$-b \oplus c-$的1的个数的奇偶性

不难发现规律若$-a \oplus b-$的popcnt为奇，$-b \oplus c-$为奇,则$-a \oplus c-$为偶

反之亦然

所以如果$-x[i] \oplus x[i-1]-$的popcnt为奇,则$-x[i]-$可以和所有不能和$-x[i-1]-$的点建边，

如果$-x[i] \oplus x[i-1]-$的popcnt为偶,则$-x[i]-$可以和所有能和$-x[i-1]-$的点建边，

那就新建一个数组，存储$-x[i]-$可向下连接的边数，称为$-p[i]-$

所以$-O(n^{2})-$变$-O(n)-$的伪代码如下

for (i,1,n)
	if (popcnt(x[i] xor x[j]) is odd){
		p[i]=i-1-p[i-1]
	else p[i]=p[i-1]
    
	ans+=p[i]

综上所述在下给出25行AC代码

#include <iostream>
#define N 10000005
using namespace std;
long long n,a,b,c,d,x[N],p[N];
unsigned long long counter=0;
int BitCount(unsigned int n){
	unsigned int c;
	for (c=0;n;++c) n&=(n-1);
	return c ;
}
int main(void){
	cin>>n>>a>>b>>c>>d>>x[0];
	a%=d;b%=d;c%=d;x[0]%=d;//暴膜
	for (unsigned int i=1;i<=n;++i){
		x[i]=((a*x[i-1])%d*x[i-1]%d+b*x[i-1]%d+c)%d;//暴膜
		long long k = x[i]^x[i-1];
			if (BitCount(k)&1!=0){
				p[i]=i-1-p[i-1];
			}
			else p[i]=p[i-1];
		counter+=p[i];
	}
	cout<<counter<<endl;
	return 0;
}

QAQ

__stdcall 坠可爱了