[toc]

题目链接：Luogu P4932。

题目

题意概括

求有多少个有序数对 $ (u, v) $ 满足 $ (x _ {u} \operatorname{xor} x _ {v}) _ {2} $ 有奇数个 $ 1 $ 。

数据范围

$$ 1 \leq n \leq 10 ^ {7}, 0 \leq x _ {i} \leq 10 ^ {9} $$

时空限制

$$\text{Luogu P4932}: 1.50 \text{s} / 500 \text{MiB} $$

题解

思路

根据异或的性质可以知道，如果 $ (x _ {u} \operatorname{xor} x _ {v}) _ {2} $，那么有 $ x _ {u} $ 与 $ x _ {v} $ 的二进制表示中，一的个数的奇偶性不同。

用 $ \operatorname{cnt} (x) $，表示 $ x $ 的二进制表示中 $ 1 $ 的个数， 那么答案就是：

$$ \sum ^ {n} _ { i = 1 } [ \frac{ \operatorname{cnt} ( x _ {i} ) – 1 }{2} \in \mathbb{Z} ] \cdot \sum ^ {n} _ { i = 1 } [ \frac{ \operatorname{cnt} ( x _ {i} ) }{2} \in \mathbb{Z} ] $$

然而这样子算法的渐进时间复杂度为 $ \Theta ( n \cdot \left\lceil \log _ {2} x _ {\max} \right\rceil ) $，把数据范围带进去算算，发现结果为 $ 298,973, 528.53986261130832874865405 \geq 4 \times 10 ^ {7} $，显然会超时。

那么我们发现，可以进行小幅度的优化，把 $ 32 $ 位的数字切开，分成两个 $ 16 $ 位数字，不影响 $ 1 $ 的个数，而 $ 16 $ 位数字总共有 $ 2 ^ {16} – 1 = 65535 $ 个，于是我们可以预处理好，加速程序。

优化后的渐进时间复杂度为 $ \Theta ( 2 ^ {\left\lfloor \frac{\left\lceil \log _ {2} x _ {\max} \right\rceil}{2} \right\rfloor} + n ) $，可以通过。

代码

注释写的很清楚。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

int n,a,b,c,d; //题目要求
int cnt[1<<16]; //cnt[] 预处理出来，cnt[i] 表示 i 中 1 的个数
ll x0,x1; //x0 为上一次的 x
ll ans[2]; // 分别存储 1 的个数为奇数和偶数的数有多少个

int main(void){
    cnt[0]=0,cnt[1]=1; //其实这行不要，把下一行改成 i=0 也可以
    for(reg int i=2;i<(1<<16);++i) //预处理 cnt[]
        cnt[i]=cnt[i>>1]+(i&1);
    n=read(),a=read(),b=read(),c=read(),d=read(),x0=read(); //按要求读入
    for(reg int i=1;i<=n;++i){
        x1=(a*x0%d*x0%d+b*x0%d+c)%d; //求出当前的 x
        reg int temp=cnt[x1>>16]+cnt[x1&((1<<16)-1)]; //切开处理
        ++ans[temp&1];
        x0=x1; //记得用 x1 覆盖 x0
    }
    printf("%lld\n",ans[0]*ans[1]); //输出答案
    return 0;
}