题目大意
求$(b)\oplus(b+a)\oplus(b+2a)\oplus\cdots\oplus(b+(n-1)a)$
其中$n,a,b\le10^9$
解题报告
因为是二进制，所以我们每一位分开考虑
又因为数$a$二进制下第$k$位的奇偶性与$a>>(k-1)$的奇偶性相同
所以对于第$k$位，我们实际是要求$\sum\limits_{x=0}^{n-1}{\left\lfloor {\frac{{ax + b}}{{{2^k}}}} \right\rfloor}$，我们将其一般化：求解$f(a,b,c,n)=\sum\limits_{x=0}^{n}{\left\lfloor {\frac{{ax + b}}{{{c}}}} \right\rfloor}$
设$s(x)=\sum\limits_{i=1}^{x}{i}$。为了只讨论$a,b<c$的情况，我们先来预处理一下：
- 若$a \ge c$那么显然$f(a,b,c,n) = f(a \% c,b,c,n) + \lfloor\frac{a}{c}\rfloor \cdot s(n)$
- 若$b \ge c$那么显然$f(a,b,c,n) = f(a,b\%c,c,n) + \lfloor\frac{b}{c}\rfloor \cdot n$
之后我们就可以施展膜法了：
设$m=\lfloor\frac{an+b}{c}\rfloor$
那么原式$=\sum\limits_{x=0}^{n}{\sum\limits_{y=0}^{m}{[y<\lfloor\frac{ax+b}{c}\rfloor]}}$
把$y<\lfloor\frac{ax+b}{c}\rfloor$提出来，可以化简：
$y<\lfloor\frac{ax+b}{c}\rfloor = c(y+1) \le ax+b = cy+c-b-1<ax=x>\lfloor\frac{cy+c-b-1}{a}\rfloor$
那么原式$=\sum\limits_{y=0}^{m}{\sum\limits_{x=0}^{n}{[x>\lfloor\frac{cy+c-b-1}{a}\rfloor]}}=n(m+1)-\sum\limits_{y=0}^m{\lfloor\frac{cy+c-b-1}{a}\rfloor}$
相当于$f(a,b,c,n)=n(m+1)-f(c,c-b\%c-1,a\%c,m)$
窝萌发现，这货的形式简直和辗转相处搞$gcd$一模一样
于是这货的复杂度也是$O(\log n)$的
当然这题还有一种数形结合的推法
推出来式子略有不同，不过时间复杂度仍然为$O(\log n)$
不过本文这种推法似乎更优？据敦敦敦讲，这货可以推广到高维
但我不会 QwQ
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
LL cal(LL a, LL b, LL c, LL n) {
if (a >= c) return (((n-1)*n/2)*(a/c)&1) ^ cal(a%c, b, c, n);
if (b >= c) return (n * (b/c) & 1) ^ cal(a, b%c, c, n);
if (!a) return (b/c) * n & 1;
LL nw = (a * (n - 1) + b) / c;
return ((n-1) * nw & 1) ^ cal(c, c - b - 1, a, nw);
}
int main() {
for (int T=read(),a,b,n;T;T--) {
n = read(); b = read();
a = read(); LL c = 1, ans = 0;
if (!b) {printf("%d\n",(n&1)?a:0); continue;}
for (int i=0;i<=60;i++,c<<=1)
ans += cal(a, b, c, n) * c;
printf("%lld\n",ans);
}
return 0;
}