[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;
}
近期评论