You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

题解 P4932 【浏览器】

. 2 min read

可爱的__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 坠可爱了



本站总访问量 正在加载今日诗词....