题解

欸，怎么忘发了

#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
const int MOD=1e9+7;
int n,k;
vector<int> cover;
vector<int> ls,rs;
vector<int> depth;
vector<int> match;
int get(int num,int pos){
	return (num>>(30-pos))&1;
}
int getval(int num,int pos){
	return num&((1<<pos)-1);
}
void extand(int idx,bool flag=false){
	if(ls[idx]) return;
	ls[idx]=cover.size();
	rs[idx]=cover.size()+1;
	cover.PB(0);
	cover.PB(0);
	ls.PB(0),ls.PB(0);
	rs.PB(0),rs.PB(0);
	depth.PB(depth[idx]+1);
	depth.PB(depth[idx]+1);
	match.PB(0);
	match.PB(0);
	if(flag){
		cover[ls[idx]]=cover[rs[idx]]=1<<(30-depth[ls[idx]]);
	}
	extand(match[idx],(cover[match[idx]]!=0));
	if(get(k,depth[idx]+1)){
		match[ls[idx]]=(rs[match[idx]]);
		match[rs[idx]]=(ls[match[idx]]);
	}
	else{
		match[ls[idx]]=(ls[match[idx]]);
		match[rs[idx]]=(rs[match[idx]]);
	}
}
void insert(int root,int l,int r,int is=0){
	if(l>r) return;
	cover[root]+=(r-l+1);
	if(r-l+1==(1<<(30-depth[root]))){
		queue<int> q;
		q.push(root);
		while(!q.empty()){
			int now=q.front();
			q.pop();
			if(now!=root){
				cover[now]+=1<<(30-depth[now]);
			}
			if(ls[now]){
				q.push(ls[now]);
				q.push(rs[now]);
				assert(rs[now]);
			}
		}
		return;
	}
	extand(root);
	int mid=is;
	mid+=1<<(30-depth[root]-1);
	insert(ls[root],l,min(r,mid-1),is);
	insert(rs[root],max(l,mid),r,mid);
}
vector<int> dp1,dp2,dp3,g1,g2,g3;
const int SIX=166666668;
void calc1(int rt){
	if(!cover[rt]) return;
	if(ls[rt]==0){
		if(cover[rt]&&cover[match[rt]]){
			dp1[rt]=1<<(30-depth[rt]);
			dp1[rt]=1ll*dp1[rt]*(getval(k,30-depth[rt])+1)%MOD;
		} 
		return;
	}
	calc1(ls[rt]);
	calc1(rs[rt]);
	dp1[rt]=dp1[ls[rt]]+dp1[rs[rt]];
	dp1[rt]%=MOD;
	if(get(k,depth[rt]+1)){
		(dp1[rt]+=1ll*cover[ls[rt]]*(cover[ls[match[rt]]])%MOD)%=MOD;
		(dp1[rt]+=1ll*cover[rs[rt]]*(cover[rs[match[rt]]])%MOD)%=MOD;
	}
}
void calc2(int rt){
	if(!cover[rt]) return;
	if(ls[rt]==0){
		if(cover[rt]&&cover[match[rt]]){
			dp2[rt]=g2[30-depth[rt]];
		}
		return;
	}
	calc2(ls[rt]);
	calc2(rs[rt]);
	dp2[rt]=dp2[ls[rt]]+dp2[rs[rt]];
	dp2[rt]%=MOD;
	if(get(k,depth[rt]+1)){
		(dp2[rt]+=(1ll*dp1[ls[rt]]*cover[rs[rt]]%MOD+1ll*dp1[rs[rt]]*cover[ls[rt]]%MOD)%MOD)%=MOD;
		(dp2[rt]+=1ll*cover[ls[rt]]*(cover[ls[rt]]-1)/2%MOD*(cover[ls[match[rt]]])%MOD)%=MOD;
		(dp2[rt]+=1ll*cover[rs[rt]]*(cover[rs[rt]]-1)/2%MOD*(cover[rs[match[rt]]])%MOD)%=MOD;
	}
}
void calc3(int rt){
	if(!cover[rt]) return;
	if(ls[rt]==0){
		if(cover[rt])
			dp3[rt]=g3[30-depth[rt]];
		return;
	}
	calc3(ls[rt]);
	calc3(rs[rt]);
	if(get(k,depth[rt]+1)){
		(dp3[rt]+=dp2[ls[rt]])%=MOD;
		(dp3[rt]+=dp2[rs[rt]])%=MOD;
		dp3[rt]+=1ll*(cover[ls[rt]])*(cover[ls[rt]]-1)%MOD*(cover[ls[rt]]-2)%MOD*SIX%MOD;
		dp3[rt]%=MOD;
		dp3[rt]+=1ll*(cover[rs[rt]])*(cover[rs[rt]]-1)%MOD*(cover[rs[rt]]-2)%MOD*SIX%MOD;
		dp3[rt]%=MOD;
	}
	else{
		dp3[rt]=dp3[ls[rt]]+dp3[rs[rt]];
		dp3[rt]%=MOD;
	}
}
int main(){
	cin>>n>>k;
	cover.PB(0);
	ls.PB(0);
	rs.PB(0);
	depth.PB(0);
	match.PB(0);
	rb(i,1,n){
		int l,r;
		cin>>l>>r;
		insert(0,l,r);
	}
	int n=cover.size()-1;
	g1.resize(n+1);
	g2.resize(n+1);
	g3.resize(n+1);
	dp1.resize(n+1);
	calc1(0);
	rb(i,0,30){
		g2[i]=1<<i;
		g2[i]=1ll*(getval(k,i)+1)*(getval(k,i))/2%MOD*g2[i]%MOD;
	}
	dp2.resize(n+1);
	calc2(0);
	dp3.resize(n+1);
	rb(i,2,30){
		if((k>>(i-1))&1){
			g3[i]+=2ll*g2[i-1]%MOD;
			g3[i]%=MOD;
			int tmp=1<<(i-1);
			tmp=2ll*tmp*(tmp-1)%MOD*(tmp-2)%MOD*SIX%MOD;
			(g3[i]+=tmp)%=MOD;
		}
		else{
			g3[i]=g3[i-1]<<1;
			g3[i]%=MOD;
		}
	}
	calc3(0);
	cout<<dp3[0];
	return 0;
}