题解

问题为求$\sum_{i=L}^R f(i \oplus x)^2$

先将区间分成两个前缀的差，现在只需要考虑$[0,R] \oplus x$

从高到低枚举最高位$w$

设$x’$表示$x$去掉第$w$位的值

设$x^w$表示只保留$x$的$[0,w-1]$位的值

如果$R<2^w$，递归到更小的$w$进行处理

如过$R\geq 2^w$，那么可以考虑$[0,R]=[0,2^w-1]+[2^w,R]$

$[0,2^w-1]\oplus x$

$=[0,2^w-1] \oplus x^w\oplus(x\oplus x^w)$

$=[0,2^w-1]\oplus(x\oplus x^w)$

$=[(x\oplus x^w),(x\oplus x^w)+2^w-1]$

（这是因为异或的逆元即为自己本身，$a\oplus x=b$等价于$b\oplus x=a$，所以$[0,2^w-1]$中的数在异或后两两互换，所以$[0,2^w-1]\oplus x^w =[0,2^w-1]$）

$[2^w,R]\oplus x = [0,R-2^w]\oplus (x\oplus 2^w)$(此处显然有$R-2^w<2^w$)，最高位变小，这部分递归到更小的$w$用相同的方法处理即可

这样就能把$[0,R]\oplus x$分成$O(logn)$个连续的区间，问题转化为求$\sum_{i=0}^R f(i)^2$

！注意！：对于异或问题，存在单调性的问题，利用数位动态规划的思想根据最高位取值为$0/1$将集合划分为两部分进行分治是很常用的做法。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 998244353;
const int M = 30;

int Q;

int get(int l,int r){
	return 0;
}

int Solve(int R,int w,int x){
	if(R==-1)return 0;
	if(w==-1)return get(x,x);//若开始传入的R=R',x=x',则此处R=0,x=x'^R',此处为递归的终止条件
	if((1<<w)>n)return Solve(R,w-1,x);
	int x1=(x>>w)<<w;//只保留大于等于m的二进制位
	int l=x1,r=x1+(1<<w)-1;
	int ret=get(l,r);
	return (ret+Solve(R-(1<<w),w-1,x^(1<<w)))%mod;
}

int main(){
	scanf("%d",&Q);
	for(int i=1,l,r,x;i<=Q;++i){
		scanf("%d%d%d",&l,&r,&x);
		printf("%d\n",(Solve(r,M-1,x)-Solve(l-1,M-1,x)+mod)%mod);	
	}
}