注意到x xor y 在二进制下1的个数是和x,y在二进制下1的个数有关
更具体的来说：一奇一偶是满足要求的
不加任何优化可以拿80分 O(nlogv)
我们又发现过程中会出现比较多的重复的数
因此可以记忆化一下
拿到90分
不过我们需要O(n)才能过
所以需要一个O(1)求x在二进制下的个数的方法
AC代码：(注意取膜的姿势)
#include<bits/stdc++.h> #define N 10000005 #define ll long long using namespace std; inline int bitcnt(ll x){ x = (x & 0x5555555555555555ll) + ((x & 0xaaaaaaaaaaaaaaaall) >> 1); x = (x & 0x3333333333333333ll) + ((x & 0xccccccccccccccccll) >> 2); x = (x & 0x0f0f0f0f0f0f0f0fll) + ((x & 0xf0f0f0f0f0f0f0f0ll) >> 4); x = (x & 0x00ff00ff00ff00ffll) + ((x & 0xff00ff00ff00ff00ll) >> 8); x = (x & 0x0000ffff0000ffffll) + ((x & 0xffff0000ffff0000ll) >> 16); x = (x & 0x00000000ffffffffll) + ((x & 0xffffffff00000000ll) >> 32); return x; } int n; ll a,b,c,d,val[N],ans; int ji,ou; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>a>>b>>c>>d>>val[0]; for(int i=1;i<=n;i++) { val[i]=(a*val[i-1]%d*val[i-1]+b*val[i-1]%d+c%d)%d; int q=bitcnt(val[i]); if(q%2==0) //偶数 { ans+=ji; ou++; } else { ans+=ou; ji++; } } cout<<ans; return 0; }