I The Yakumo Family

题目大意:：给定长度为$nn$的数列$a[]a[]$，定义$f(l,r)={\oplus }_{i=l}^{r}a[i]f(l,r)=\backslash oplus^r\_\{i=l\}a[i]$,求下式:

$\sum _{1\le l1\le r1\le l2\le r2\le l3\le r3\le n}f(l1,r1)\ast f(l2,r2)\ast f(l3,r3)\backslash sum\backslash limits\_\{1\backslash le\; l1\backslash le\; r1\; \backslash le\; l2\; \backslash le\; r2\; \backslash le\; l3\; \backslash le\; r3\; \backslash le\; n\}\; f(l1,r1)*f(l2,r2)*f(l3,r3)$
$\mathrm{其}\mathrm{中}1\le n\le 2\ast 10^5,1\le m\le 2\ast 10^5其中1\backslash le\; n\backslash le\; 2*10^5,1\backslash le\; m\; \backslash le\; 2*10^5$

解题思路:可以逐位考虑，分别计算贡献。
$----------------$首先可以考虑计算$\sum _{1\le l1\le r1\le n}f(l1,r1)\backslash sum\backslash limits\_\{1\backslash le\; l1\backslash le\; r1\; \backslash le\; n\}f(l1,r1)$
设$s_{i}s\_i$表示第i个数对答案的贡献，$pr{e}_{i}pre\_i$为序列的异或前缀和,由异或的性质可知若$pr{e}_{i}pre\_i$二进制下第$bitbit$位为$11$，则需要寻找${\sum }_{j=1}^{i-1}pr{e}_j=0\backslash sum^\{i-1\}\_\{j=1\}pre\_j=0$，才会对答案有贡献，显然这是可以预处理的。
$\mathrm{此}\mathrm{题}此题$: 链接

参考代码：

#define LL long long
using namespace std;
const int M=1e5+7;
const LL Mod=998244353;
int n;
LL anq=0;
LL a[M],s[M],pre[M],P[3];
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	pre[0]=0;
	pre[1]=a[1];
	for(int i=2;i<=n;i++){
		pre[i]=pre[i-1]^a[i];
	}
	for(int bit=0;bit<=20;bit++){
		P[0]=1;P[1]=0;
		for(int i=1;i<=n;i++){
			if((pre[i]>>bit)&1){
				 s[i]=P[0];  P[1]++;
			} else {
				 s[i]=P[1];  P[0]++;
			}
			anq=anq+s[i]*(1<<bit);
		}
	}
	cout<<anq<<"\n";
}

接下来，可以考虑求$\sum _{1\le l1\le r1\le l2\le r2\le n}f(l1,r1)\ast f(l2,r2)\backslash sum\backslash limits\_\{1\backslash le\; l1\backslash le\; r1\; \backslash le\; l2\; \backslash le\; r2\; \backslash le\; n\}f(l1,r1)*f(l2,r2)$
首先还是考虑拆位。设$s[k][i]\mathrm{表}\mathrm{示}\mathrm{考}\mathrm{虑}\mathrm{第}k\mathrm{个}\mathrm{区}\mathrm{间}\mathrm{时}\mathrm{该}\mathrm{区}\mathrm{间}\mathrm{右}\mathrm{端}\mathrm{点}\mathrm{为}i\mathrm{时}\mathrm{的}\mathrm{贡}\mathrm{献}s[k][i]表示考虑第k个区间时该区间右端点为i时的贡献$，考虑当$r2r2$固定时，可以枚举$l2l2$，如果此区间$(l2,r2)(l2,r2)$在此位上异或值为$11$，那么对答案贡献便为$s[1][l2-1]s[1][l2-1]$,即第一区间的右端点在$(l2-1)(l2-1)$上。因而可以考虑随着$l2l2$增 大维护数组$P_0,P_{1}P\_0,P\_1$表示该位上前缀异或和为$00$或$11$的$s_{1,l2}s\_\{1,l2\}$的贡献和。
此题k=3,同理可推
注意到$s[k][i]\mathrm{只}\mathrm{与}s[k-1][\mathrm{.}\mathrm{.}]\mathrm{有}\mathrm{关}\mathrm{，}\mathrm{故}\mathrm{可}\mathrm{以}\mathrm{采}\mathrm{用}\mathrm{滚}\mathrm{动}\mathrm{数}\mathrm{组}s[k][i]只与s[k-1][..]有关，故可以采用滚动数组$

参考代码:

#define LL long long
using namespace std;
const int M=2e5+7;
const LL Mod=998244353;
int n;
LL anq=0;
LL a[M],s[M],pre[M],P[3],ss[M];
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	s[0]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]^a[i];
		s[i]=1;
	}
	for(int k=1;k<=3;k++){
		for(int bit=0;bit<=30;bit++){
			P[0]=P[1]=0;
			if(k==1) P[0]=1; //P[x=0/1] 表示之前在 x 前放 k-1 个不相交的区间，所有方案下这些区间的权值和 
		    for(int i=1;i<=n;i++){
			    ss[i]=(ss[i]+(P[((pre[i]>>bit)&1)^1]<<bit))%Mod;
			    P[(pre[i]>>bit)&1]=(1ll*P[(pre[i]>>bit)&1]+s[i])%Mod;
			    //cout<<k<<" "<<bit<<" "<<i<<":"<<P[0]<<" "<<P[1]<<" "<<ss[i]<<"\n";
		    }
	    }
		s[0]=0;
		for(int i=1;i<=n;i++){
		    s[i]=(s[i-1]+ss[i])%Mod;
		    ss[i]=0;
		}
	}
	cout<<s[n]<<"\n";
}