题目背景

__stdcall在用(Edge)玩(slay)的时候，鼠标会经常失灵，这让她十分痛苦，因此她决定也要让你们感受一下(Edge)制造的痛苦。

题目描述

__stdcall给了你(n)个点，第(i)个点有权值(x[i])，对于两个点(u)和(v)，如果(x[u] xor x[v])的结果在二进制表示下有奇数个(1)，那么在(u)和(v)之间连接一个(Edge)，现在__stdcall想让你求出一共有多少个(Edge)。

如果你没能成功完成任务，那么__stdcall会让你痛苦一下，你这个测试点就没分了。

输入输出格式

输入格式：

一行六个整数，(n,a,b,c,d,x[0])。

(n)是点的个数，每个点的权值需要用如下的方式生成。

你需要使用(a,b,c,d)和(x[0])生成一个数组(x)，生成方式是这样的。

[x_i=(ax_{i-1}^2+bx_{i-1}+c)mod d ]

(x[i])就是第(i)个点的权值，点的标号是(1)到(n)。

输出格式：

输出一个整数，表示一共有多少个(Edge)。

输入输出样例

输入样例#1：

8 98 24 20 100 44

输出样例#1：

输入样例#2：

1000 952537 601907 686180 1000000 673601

输出样例#2：

说明

我们用(v)表示权值中的最大值。

对于前(20\%)的数据，(nleq 10)。

对于前(40\%)的数据，(nleq 100)。

对于前(60\%)的数据，(nleq 1000)。

对于前(80\%)的数据，(nleq 1e6)。

对于前(90\%)的数据，(vleq 1e6)。

对于(100\%)的数据，(nleq 1e7,vleq1e9)。

保证(a,b,c,d,x[0])都是(int)内的非负整数。

思路

O(n^2)做法：

我们直接把(x)数组搞出来，然后暴力两两匹配看两者的异或值的二进制表示是否只有一个(1)，逐个统计答案。

O(n)做法：

这题的做法是真的好玩。其实就是一个结论：两个数字的异或值在二进制表示下为奇数，当且仅当两个数字的二进制表示中(1)的个数一个为奇数，一个为偶数。

比如说两个偶数(a,b)，它们的二进制表示下有(x)位同为(1)，有(y)位(a)是(1)而(b)是零，有(z)位(a)是(0)而(b)是(1)，那么((x+y)mod 2=0)，且((x+z)mod 2=0)，所以有((x+y+x+z)mod 2=0)，也就是((y+z)mod 2=0)。其他情况证明相同。

所以只需要统计出所有数中二进制表示中(1)的个数为奇数的数的个数与为偶数的数的个数，相乘得到答案。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,a,b,c,d,ans[2],x;
LL read()
{
    LL re=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
    return re;
}
int main()
{
    n=read(),a=read(),b=read(),c=read(),d=read(),x=read();
    a%=d,b%=d,c%=d,x%=d;
    for(LL i=1;i<=n;i++) x=(a*x%d*x%d+b*x%d+c)%d,ans[__builtin_popcount(x)&1]++;
    printf("%lld",ans[0]*ans[1]);
    return 0;
}

Luogu P4932 浏览器(二进制) 题意 思路 AC代码