洛谷 4932 洛谷10月月赛II T1 浏览器

【题解】

　　x xor y的结果在二进制下有奇数个1，等价于x与y在二进制下的1的个数之和为奇数，因为x xor y减少的1的个数一定是偶数（两个数这一位都为1，xor的结果为0，减少了2个1）

　　那么答案就是序列中二进制下有奇数个1的数的个数乘二进制下有偶数个1的数的个数。

　　因为n有1e7，暴力算每个数二进制下1的个数是不行的。我们需要预处理0~2^15的Popcount，把每个数掐成高低两段统计。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 10000010

 using namespace std;

 int n,Popcount[],a,b,c,d,x,odd,even;

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 int main(){

     for(rg int i=;i<;i++) Popcount[i]=Popcount[i&(i-)]+;

     n=read(); a=read(); b=read(); c=read(); d=read(); x=read();

     for(rg int i=;i<=n;i++){

         x=(1ll*a*x%d*x+1ll*b*x+c)%d;

         int tmp=Popcount[x>>]+Popcount[x&];

         if(tmp&) odd++; else even++;

     }

     printf("%lld\n",1ll*odd*even);

     return ;

 }

巴特西

洛谷 4932 洛谷10月月赛II T1 浏览器

最新文章

热门文章