【异或/找规律】 T44755 浏览器

T44755 浏览器

（窝第一次打洛咕月赛QAQ...写完T1就跑去干别的了QAQ..

第二天发现评分是蓝题，惊了orz

思路

如果一个数在二进制表示下有奇数个1，（先叫它奇数吧QAQ，偶数同理
手玩一下你会发现，奇数^偶数结果一定符合要求， ans+1, 其余情况均不符合要求
所以只要翻译一下题面求一下x[i]数组，统计一下x数组中有多少奇数多少偶数(平常的那种qaq
相乘就是答案qwq

注意

模就要一直模QAQ多模两遍没坏处！
x数组会爆int ——>所以开个long long也没坏处QAQ！！！

 1 #include<cstdio>
 2 #include<iostream>
 3 #define ll long long
 4 using namespace std;
 5 const int sz = 10000010;
 6 int n, a, b, c, d,ans = 0; 
 7 ll js = 0, os = 0, x[sz];
 8 int countbit(int x) {
 9     int cnt = 0;
10     while(x) {
11         cnt++;
12         x &= x-1;
13     }
14     return cnt;
15 }
16 int main() {
17     scanf("%d%d%d%d%d%d", &n, &a, &b, &c, &d, &x[0]);
18     a %= d, b %= d, c %= d;
19     for(int i = 1; i <= n; i++) {
20         x[i] = ((a*x[i-1])%d*x[i-1])%d + (b*x[i-1])%d + c;
21         x[i] %= d;
22     }
23     for(int i = 1; i <= n; i++) {
24         int mid;
25         mid = countbit(x[i]);
26         if(mid&1) js++;
27         else os++;
28     }
29     printf("%lld", js*os);
30     return 0;
31 }