P4932 浏览器 题解

CSDN同步

原题链接

简要题意:

给定 (n) 个点的权值 (x_i),求 (u ot = v)(x_u space ext{xor} space x_v) 有奇数个 (1) 的个数。

算法一

对于前 (60 \%) 的数据,(n leq 1000).

很简单啊,直接枚举两个点,然后 ( ext{xor}) 一下就可以了。

时间复杂度:(O(n^2)).

实际得分:(60pts).

算法二

对于前 (80 \%) 的数据,(n leq 10^6)(v leq 10^6).((v = max_{i=1}^n x_i)

显然,我们考虑 ( ext{xor}) 的性质。

( ext{xor}) 如果两位相同则为 (0),否则为 (1);它不会改变 两个数 (1) 的个数之和,因为 (1) 要么两个两个被计算掉,要么一个个被保留。

所以,用 (f_i) 表示 (x_i) 二进制下 (1) 的个数,本题变为:

(f_i + f_j) 为奇数的个数,这个统计奇偶就可以了。

关键如何统计二进制下 (1) 的个数?暴力转进制即可。

时间复杂度:(O(n log v)).

实际得分:(80pts).

算法三

优化求 (1) 的个数的过程即可。

可以用 ( ext{\_\_builtin \_parity}) 优化(( ext{CSP / NOIP}) 不支持啊),不过手测 (O(n log v)) 过了。

时间复杂度:(O(n)).

实际得分:(100pts).

// tot[__builtin_parity(x=((a*x%d)*x%d+b*x%d+c)%d)&1]++; 等同于:
// x=((a*x%d)*x%d+b*x%d+c)%d;
// tot[__builtin_parity(x)&1]++;
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

ll n,a,b,c,d,x;
ll tot[2]; //统计奇偶

int main(){
	n=read(),a=read(),b=read(),c=read(),d=read(),x=read();
	a%=d,b%=d,c%=d,x%=d; for(int i=1;i<=n;i++)
		tot[__builtin_parity(x=((a*x%d)*x%d+b*x%d+c)%d)&1]++;
	printf("%lld
",tot[0]*tot[1]);	
	return 0;
}

原文地址:https://www.cnblogs.com/bifanwen/p/12678733.html