可爱的__stdcall大佬都说得非常明白了
毕竟是出题人
但是本蒟蒻发现自己的$O(n)$方法好像不太一样...
首先是一个玄学的popcnt统计代码
int BitCount(unsigned int n){
unsigned int c=0;
for (c=0;n;++c){//遍历n的最小的1的位置
n&=(n-1);//将n移到最小的1的位
}
return c ;
}
既然需要对所有的边都进行判定,那么按照暴力的想法,需要写一个双重循环去暴力判定
如下伪代码:
for (i,1,n)
for (j,1,i-1)
if ( popcnt(x[i] xor x[j]) is odd)
ans++
这么暴力一定会被续的
所以就要考虑 $-x[i]-$ 和 $-x[i-1]-$ 对结果的贡献了
考虑若$-a \oplus b-$与$-a \oplus c-$与$-b \oplus c-$的1的个数的奇偶性
不难发现规律若$-a \oplus b-$的popcnt为奇,$-b \oplus c-$为奇,则$-a \oplus c-$为偶
反之亦然
所以如果$-x[i] \oplus x[i-1]-$的popcnt为奇,则$-x[i]-$可以和所有不能和$-x[i-1]-$的点建边,
如果$-x[i] \oplus x[i-1]-$的popcnt为偶,则$-x[i]-$可以和所有能和$-x[i-1]-$的点建边,
那就新建一个数组,存储$-x[i]-$可向下连接的边数,称为$-p[i]-$
所以$-O(n^{2})-$变$-O(n)-$的伪代码如下
for (i,1,n)
if (popcnt(x[i] xor x[j]) is odd){
p[i]=i-1-p[i-1]
else p[i]=p[i-1]
ans+=p[i]
综上所述在下给出25行AC代码
#include <iostream>
#define N 10000005
using namespace std;
long long n,a,b,c,d,x[N],p[N];
unsigned long long counter=0;
int BitCount(unsigned int n){
unsigned int c;
for (c=0;n;++c) n&=(n-1);
return c ;
}
int main(void){
cin>>n>>a>>b>>c>>d>>x[0];
a%=d;b%=d;c%=d;x[0]%=d;//暴膜
for (unsigned int i=1;i<=n;++i){
x[i]=((a*x[i-1])%d*x[i-1]%d+b*x[i-1]%d+c)%d;//暴膜
long long k = x[i]^x[i-1];
if (BitCount(k)&1!=0){
p[i]=i-1-p[i-1];
}
else p[i]=p[i-1];
counter+=p[i];
}
cout<<counter<<endl;
return 0;
}
QAQ
__stdcall 坠可爱了