题目大意：给你一个序列，求满足$x_{i}\: xor\; x_{j}$在二进制下1的数量为奇数的数对数量
打月赛的时候真没想出来，还是我太弱..
xor意义下，对于两个数，假设它们两个每一位都是2个0，或者一个1一个0，那么xor之后的数中1的数量是直接相加
如果有同一位有2个1，两个1xor会变成0，1的总数量-2，也不会影响1数量的奇偶性
那么我们只需要统计二进制下，奇数个1的数的个数，和偶数个1的数的个数即可
统计的过程要用到一个套路，预处理出0~(2^16)里每个数中1的数量
一个数中1的数量就是高16位和低16位中1的数量相加嘛
注意，询问的序列是从1开始的！因为这个我调了半天！
1 // luogu-judger-enable-o2 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #define N 10000010 7 #define ll long long 8 #define ui unsigned int 9 #define maxn (1<<16) 10 #define rint register int 11 using namespace std; 12 //re 13 14 int gint() 15 { 16 int ret=0,fh=1;char c=getchar(); 17 while(c<‘0‘||c>‘9‘){if(c==‘-‘)fh=-1;c=getchar();} 18 while(c>=‘0‘&&c<=‘9‘){ret=ret*10+c-‘0‘;c=getchar();} 19 return ret*fh; 20 } 21 int n; 22 ll A,B,C,D; 23 ui x[N]; 24 int cnt[(1<<17)+100]; 25 26 int main() 27 { 28 scanf("%d%lld%lld%lld%lld%u",&n,&A,&B,&C,&D,&x[0]); 29 for(rint i=1;i<=n;i++) 30 x[i]=((1ll*A*x[i-1]%D*x[i-1]%D+1ll*B*x[i-1]%D)%D+C)%D; 31 for(int i=0;i<(1<<16);i++) 32 cnt[i]=cnt[i>>1]+(i&1); 33 ll odd=0,eve=0; 34 for(rint i=1;i<=n;i++){ 35 int num=cnt[x[i]&((1<<16)-1)]+cnt[(x[i])>>16]; 36 if(num&1){odd++;} 37 else {eve++;} 38 } 39 printf("%lld\n",odd*eve); 40 return 0; 41 }
原文：https://www.cnblogs.com/guapisolo/p/9865065.html