题解

定义序列$a_{1…n}$的权值为$\sum a_i$

求满足$l_i \leq a_i \leq r_i$且$a_i$单调不降的所有序列$a_{1…n}$的权值和。

考虑最高位，那么一定存在一个$k$，使得$a[1…k]$最高位是$0$，$a[k+1…n]$最高位是$1$，那么可以分成两个子区间去做。

设$f[i][L][R][LIML][LIMR]$表示：在$i+1…60$位已经定下来的情况下（此时$a[L…R]$的$i+1..60$位的值一样），区间$[L…R]$只考虑$1…i$位的答案。

$LIML$表示只考虑$i+1..60$位$a[L…R]$是否等于区间中最大的$l_x$；

$LIMR$表示只考虑$i+1..60$位$a[L…R]$是否等于区间中最小的$r_x$

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

代码

struct atom{
	int sumw,way;
	atom(int _sumw=0,int _way=0){
		sumw=_sumw;
		way=_way;
	}
	friend atom operator +(atom a,atom b){
		return atom((a.sumw+b.sumw)%mod,(a.way+b.way)%mod);
	}
	friend atom operator *(atom a,atom b){
		return atom((a.sumw*1ll*b.way+a.way*1ll*b.sumw)%mod,a.way*1ll*b.way%mod);
	}
};

void Solve(){
	for(int i=1;i<=n;++i){
		mir[i][i]=r[i];
		mal[i][i]=l[i];
		for(int j=i+1;j<=n;++j){
			mir[i][j]=min(mir[i][j-1],r[j]);
			mal[i][j]=max(mal[i][j-1],l[j]);
		}
	}	
	for(int l=1;l<=n;++l)
	for(int r=l;r<=n;++r)
	for(int el=0;el<2;++el)
	for(int er=0;er<2;++er){
		f[0][l][r][el][er]=atom(0,1);
	}
	for(int i=1;i<=60;++i){
		for(int l=1;l<=n;++l)
		for(int r=l;r<=n;++r)
		for(int el=0;el<2;++el)
		for(int er=0;er<2;++er){
			atom ans=atom(0,0);
			for(int k=l;k<=r-1;++k){
				//第i位a[l...k]填0,a[k+1..r]填1
				//如果(i+1,60)位mal[l][k]小于mal[l][r],那么由于LIML=1,所以a[l...r]的(i+1,60)位均等于mal[l][r],所以a[l...k]的(i+1,60)位小于mal[l][k]，所以子区间的LIML一定为0
				int lel=(el&&(mal[l][k]>>i)==(mal[l][r]>>i));
				int ler=(er&&(mir[l][k]>>i)==(mir[l][r]>>i));
				int rel=(el&&(mal[k+1][r]>>i)==(mal[l][r]>>i));
				int rer=(er&&(mir[k+1][r]>>i)==(mir[l][r]>>i));
				//判断第i位a[l...k]填0,a[k+1..r]填1是否可行以及子区间LIML,LIMR的变化
				if(lel&&(mal[l][k]&(1ll<<(i-1))))continue;
				if(rer&&(!(mir[k+1][r]&(1ll<<(i-1)))))continue;
				ler&=((mir[l][k]&(1ll<<(i-1)))==0);
				rel&=((mal[k+1][r]&(1ll<<(i-1)))>0);
				ans=(ans+f[i-1][l][k][lel][ler]*f[i-1][k+1][r][rel][rer]*atom((r-k)*1ll*((1ll<<(i-1))%mod)%mod,1));
			}
			//第i位全填0
			if(el&&(mal[l][r]&(1ll<<(i-1))));
			else{
				int nl=el;
				int nr=er&&((mir[l][r]&(1ll<<(i-1)))==0);
				ans=(ans+f[i-1][l][r][nl][nr]*atom(0,1));
			}
			//第i位全填1
			if(er&&(!(mir[l][r]&(1ll<<(i-1)))));
			else{
				int nl=el&&(mal[l][r]&(1ll<<(i-1)));
				int nr=er;
				ans=(ans+f[i-1][l][r][nl][nr]*atom((r-l+1)*1ll*((1ll<<(i-1))%mod)%mod,1));
			}
			f[i][l][r][el][er]=ans;
		}
	}
	printf("%d\n",f[60][1][n][1][1].sumw);
}