洛谷题解

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
   x=0;char c=getchar();T neg=1;
   while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
   while(isdigit(c)) x=x*10+c-'0',c=getchar();
   x*=neg;
}
const int MAXN=2e4;
const int LOG_N=30;
const int MAXT=1e6;
const int MAX=(1<<LOG_N)-1;
const int MOD=1e9+7;
const int TWO=5e8+4;
const int SIX=166666668;
int n,k,siz[MAXT+5],ch[MAXT+5][2],ncnt=LOG_N+1,rt=LOG_N+1,dep[MAXT+5];
bool isend[MAXT+5];
void update(int &k,int l,int r,int nl,int nr,int d){
   if(l==nl&&nr==r){k=LOG_N-d;return;}
   if(!~k) k=++ncnt,dep[k]=d;int mid=(l+r)>>1;
//	printf("%d %d %d %d %d %d\n",k,l,r,nl,nr,d);
   if(nr<=mid) update(ch[k][0],l,mid,nl,nr,d+1);
   else if(nl>mid) update(ch[k][1],mid+1,r,nl,nr,d+1);
   else update(ch[k][0],l,mid,nl,mid,d+1),update(ch[k][1],mid+1,r,mid+1,nr,d+1);
   siz[k]=siz[ch[k][0]]+siz[ch[k][1]];
}
int dp1[MAXT+5];
map<int,int> dp2[MAXT+5],dp3[MAXT+5];
int calc1(int x);
int calc2(int x,int y);
int calc3(int x,int y);
//calc1: 3 nodes in subtree of x
//calc2: 2 nodes in subtree of x and 1 node in subtree of y
//calc3: 1 nodes in subtree of x and 1 node in subtree of y
int calc1(int x){
//	if(x==0||x==1) return 0;
   if(~dp1[x]) return dp1[x];
   dp1[x]=0;
   if(~ch[x][0]){
   	if(k>>(LOG_N-dep[x]-1)&1) dp1[x]=(dp1[x]+1ll*siz[ch[x][0]]*(siz[ch[x][0]]-1)%MOD*(siz[ch[x][0]]-2)%MOD*SIX%MOD)%MOD;
   	else dp1[x]=(dp1[x]+calc1(ch[x][0]))%MOD;
   }
   if(~ch[x][1]){
   	if(k>>(LOG_N-dep[x]-1)&1) dp1[x]=(dp1[x]+1ll*siz[ch[x][1]]*(siz[ch[x][1]]-1)%MOD*(siz[ch[x][1]]-2)%MOD*SIX%MOD)%MOD;
   	else dp1[x]=(dp1[x]+calc1(ch[x][1]))%MOD;
   }
   if(~ch[x][0]&&~ch[x][1]) if(k>>(LOG_N-dep[x]-1)&1){
   	dp1[x]=(dp1[x]+calc2(ch[x][0],ch[x][1]))%MOD;
   	dp1[x]=(dp1[x]+calc2(ch[x][1],ch[x][0]))%MOD;
   }
//	printf("%d %d\n",x,dp1[x]);
   return dp1[x];
}
int calc2(int x,int y){
//	if(!x) return 0;
   if(dp2[x].find(y)!=dp2[x].end()) return dp2[x][y];
   dp2[x][y]=0;
   if(~ch[x][0]&&~ch[y][0]){
   	if(k>>(LOG_N-dep[x]-1)&1)
   		dp2[x][y]=(dp2[x][y]+1ll*siz[ch[x][0]]*(siz[ch[x][0]]-1)%MOD*TWO%MOD*siz[ch[y][0]]%MOD)%MOD;
   	else dp2[x][y]=(dp2[x][y]+calc2(ch[x][0],ch[y][0]))%MOD;
   }
   if(~ch[x][0]&&~ch[y][1]) if(k>>(LOG_N-dep[x]-1)&1) dp2[x][y]=(dp2[x][y]+calc2(ch[x][0],ch[y][1]))%MOD;
   if(~ch[x][0]&&~ch[x][1]&&~ch[y][0]) if(k>>(LOG_N-dep[x]-1)&1) dp2[x][y]=(dp2[x][y]+1ll*calc3(ch[x][1],ch[y][0])*siz[ch[x][0]]%MOD)%MOD;
   if(~ch[x][0]&&~ch[x][1]&&~ch[y][1]) if(k>>(LOG_N-dep[x]-1)&1) dp2[x][y]=(dp2[x][y]+1ll*calc3(ch[x][0],ch[y][1])*siz[ch[x][1]]%MOD)%MOD;
   if(~ch[x][1]&&~ch[y][0]) if(k>>(LOG_N-dep[x]-1)&1) dp2[x][y]=(dp2[x][y]+calc2(ch[x][1],ch[y][0]))%MOD;
   if(~ch[x][1]&&~ch[y][1]){
   	if(k>>(LOG_N-dep[x]-1)&1)
   		dp2[x][y]=(dp2[x][y]+1ll*siz[ch[x][1]]*(siz[ch[x][1]]-1)%MOD*TWO%MOD*siz[ch[y][1]]%MOD)%MOD;
   	else dp2[x][y]=(dp2[x][y]+calc2(ch[x][1],ch[y][1]))%MOD;
   }
//	printf("c2 %d %d %d\n",x,y,dp2[x][y]);
   return dp2[x][y];
}
int calc3(int x,int y){
   if(!x) return 1;
   if(dp3[x].find(y)!=dp3[x].end()) return dp3[x][y];
   dp3[x][y]=0;
   if(~ch[x][0]&&~ch[y][0]){
   	if(k>>(LOG_N-dep[x]-1)&1) dp3[x][y]=(dp3[x][y]+1ll*siz[ch[x][0]]*siz[ch[y][0]]%MOD)%MOD;
   	else dp3[x][y]=(dp3[x][y]+calc3(ch[x][0],ch[y][0]))%MOD;
   }
   if(~ch[x][0]&&~ch[y][1]) if(k>>(LOG_N-dep[x]-1)&1) dp3[x][y]=(dp3[x][y]+calc3(ch[x][0],ch[y][1]))%MOD;
   if(~ch[x][1]&&~ch[y][0]) if(k>>(LOG_N-dep[x]-1)&1) dp3[x][y]=(dp3[x][y]+calc3(ch[x][1],ch[y][0]))%MOD;
   if(~ch[x][1]&&~ch[y][1]){
   	if(k>>(LOG_N-dep[x]-1)&1) dp3[x][y]=(dp3[x][y]+1ll*siz[ch[x][1]]*siz[ch[y][1]]%MOD)%MOD;
   	else dp3[x][y]=(dp3[x][y]+calc3(ch[x][1],ch[y][1]))%MOD;
   }
//	printf("c3 %d %d %d\n",x,y,dp3[x][y]);
   return dp3[x][y];
}
int main(){
   fill1(ch);
   siz[0]=1;for(int i=1;i<=LOG_N;i++) ch[i][0]=ch[i][1]=i-1,siz[i]=(1<<i),dep[i]=LOG_N-i;
   memset(dp1,-1,sizeof(dp1));scanf("%d%d",&n,&k);
   for(int i=1;i<=n;i++){int l,r;scanf("%d%d",&l,&r);update(rt,0,MAX,l,r,0);}
//	for(int i=0;i<=ncnt;i++) printf("%d %d %d %d\n",ch[i][0],ch[i][1],dep[i],siz[i]);
   printf("%d\n",calc1(rt));
   return 0;
}