Luogu P4932 浏览器

题目描述

https://www.luogu.com.cn/problem/P4932

简要题意：给定 $n$ 个数，求有多少对数，满足异或有奇数个 $1$

$n\le 10^7$

Solution

异或只会消掉两个 $1$，不会改变奇偶性

所以答案就是奇数个 $1$ 的个数乘以偶数个 $1$ 的个数

至于如何 $O(1)$，可以预处理 $2^{16}$

#include <iostream>
#include <cstdio>
#define maxn 500010
#define ll long long 
using namespace std;

ll n, a, b, c, d, x; 

#define N 65535
int Bit[N + 1]; 
void init_Bit() {
    for (int i = 0, s = 0; i <= N; Bit[i++] = s, s = 0) 
        for (int j = 0; j < 16; ++j) s += i >> j & 1;
} 

ll s1, s2;
int main() {
    cin >> n >> a >> b >> c >> d >> x; init_Bit(); 
    for (int i = 1; i <= n; ++i) {
        int s = 0; x = (a * x % d * x + b * x + c) % d;
        s += Bit[x & N];
        s += Bit[x >> 16];
        if (s & 1) ++s1;
        else ++s2;
    } cout << s1 * s2 << endl; 
    return 0;
}