USACO2020DEC Gold/Platinum 解题报告 USACO2020DEC Gold/Platinum 解题报告
补完了耶
Gold T1
题意概括
给定(n imes n)的方格图,一些位置为障碍,一些位置为可能的起点.若将一个可能的位置放上机器人,可以往四个方向走,且每(D)秒会变大1(曼哈顿意义上的).求机器人所有可能的覆盖位置.
(nle 1000,1le D le10^9)
题解
Observation: 考虑到(Dge1),因而每走至少一格才会变大1,为了到达一个位置而等待扩展部分到达该位置不如直接去走到对应位置(考虑机器人变大更难通过障碍).
自此我们得到对应的算法框架:对于所有的起点S,bfs得到能通过最短路走到的所有位置,然后对于所有可到达的位置计算扩展部分.
对于第一部分,我们考虑提前用一次bfs去计算每个点到最近边界的距离,这样就相当于给每一个点一个时间限制.
对于第二个部分,一种可行的方法是转坐标系然后二维差分,然而比较难写.一种更为简单的写法是再去bfs一遍,注意到一个点可能被到达多次,我们用优先队列维护,只取k最大的一次即可
Code
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define DEBUG printf("Passing Line %d in function [%s].
",__LINE__,__FUNCTION__)
using namespace std;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ztr;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
x*=f;
}
template<typename T>inline void write(T x){
if(!x)putchar('0');
if(x<0)x=-x,putchar('-');
static int sta[40];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
const int maxn=2007,INF=0x3f3f3f3f;
const ll MOD=998244353;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
int n,D;
char s[maxn];
int a[maxn][maxn];
int dis[maxn][maxn];
vector<pii> v;
queue<pii > q;
queue<pair<pii,int > > qs;
bool is_good(int x,int y){
return (x>=1)&&(x<=n)&&(y>=1)&&(y<=n);
}
inline void init_dis(){
while(!q.empty()){
int x=q.front().fi,y=q.front().se;
q.pop();
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(is_good(nx,ny)&&dis[nx][ny]==-1)dis[nx][ny]=dis[x][y]+1,q.push(mp(nx,ny));
}
}
}
int vis[maxn][maxn];
priority_queue<pair<int ,pii> > pq;
inline void flood_fill(){
while(!qs.empty()){
int x=qs.front().fi.fi,y=qs.front().fi.se,rt=qs.front().se;
qs.pop();
if(vis[x][y]||rt/D>dis[x][y])continue;
pq.push(mp(min(rt/D+1,dis[x][y]-1),mp(x,y)));
if(rt/D==dis[x][y])continue;
vis[x][y]=1;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(!vis[nx][ny]&&is_good(nx,ny)&&dis[nx][ny]>(rt)/D)qs.push(mp(mp(nx,ny),rt+1));
}
}
}
int ans=0;
inline void getans(){
memset(vis,0,sizeof(vis));
while(!pq.empty()){
int x=pq.top().se.fi,y=pq.top().se.se,rt=pq.top().fi;
pq.pop();
if(vis[x][y])continue;
vis[x][y]=1;
ans++;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(a[nx][ny]==1&&is_good(nx,ny)&&!vis[nx][ny]&&rt>0)pq.push(mp(rt-1,mp(nx,ny)));
}
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
memset(dis,-1,sizeof(dis));
scanf("%d%d",&n,&D);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=n;j++){
if(s[j]=='#')a[i][j]=0,q.push(mp(i,j)),dis[i][j]=0;
else if(s[j]=='S')a[i][j]=1,qs.push(mp(mp(i,j),0));
else a[i][j]=1;
}
}
init_dis();
flood_fill();
getans();
printf("%d
",ans);
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case
Gold T2
题意概括
不概括了,自己看
题解
Observation: 注意到一个非常重要的事实,由于我们是将所有连续相同字符之间的位置切开,因而对于一个串,它对应的结果串是唯一的。所以对于结果串而言,一种合法划分即对应一种合法初始串。
那么什么样的串是合法串呢？显然的有两个条件：
- 每一段划分中间不能有连续相同字符，不然我们一定会在那个位置将其割开。
- 对于划分中的连续两个子串(s,t)，(s)的首字符必须等于(t)的末字符，不然我们也不会去割那个位置。
不难证明这是一个充分必要条件。
由此可以得到一个朴素的DP想法，考虑(dp[i][ch])表示已经把前i个字符割好了，且最后一个子串的首字母为ch，转移时从大往小枚举前一个划分位置(j)，判断(s[j+1ldots i])有无连续相同字符即可。这个东西的复杂度是(Theta(n^2))的，无法接受。
考虑优化。在这种划分问题中，有一个套路是考虑i时要么加入前一个划分，要么另起一段。这道题中也是同样的道理。令(dp[i][a][b][c])表示最后一段最后一个字母为a，首字母为b，倒数第二段为c。
这样，对于(s[i+1])来说，若(s[i+1]!=a)，那么自然可以添加进最后一段。若(a=c)，那么最后一段就可以结束，让(s[i+1])自成一段。
这样复杂度即为(Theta(n))，转移时有一个(|Sigma|^4)级别的常数，此题(|Sigma|)为4，所以没有问题。
Code
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define DEBUG printf("Passing Line %d in function [%s].
",__LINE__,__FUNCTION__)
using namespace std;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ztr;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
x*=f;
}
template<typename T>inline void write(T x){
if(!x)putchar('0');
if(x<0)x=-x,putchar('-');
static int sta[40];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
const int maxn=200007,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
char s[maxn];
int n;
int dp[maxn][4][4][4];
const char to[]="AGCT";
int ans=0;
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(s[1]=='?'||s[1]==to[j])dp[1][j][j][i]=1;
}
}
for(int i=2;i<=n;i++){
for(int a=0;a<4;a++){
if(s[i]!='?'&&s[i]!=to[a])continue;
for(int b=0;b<4;b++){
for(int c=0;c<4;c++){
for(int la=0;la<4;la++){
if(la!=a)add(dp[i][a][b][c],dp[i-1][la][b][c]);
if(la==c)add(dp[i][a][a][b],dp[i-1][la][b][c]);
}
}
}
}
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
add(ans,dp[n][i][j][i]);
}
}
printf("%d",ans);
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case
Gold T3
题意概括
请用您勤劳的双手自己查看。
做法
没啥意思的题，口胡一下。
枚举最左和最右的两只奶牛，然后双指针扫一下竖直方向即可。复杂度(Theta(n^3log n))到(Theta(n^3))左右。
细节比较多，懒得写了。
Pt T1
题意概括
给定长度为(n)的(a_i,b_i)，当且仅当(a_ile b_j)时能匹配，问极大匹配数。
(nle 2000)
题解
发现USACO考这种牛逼DP挺多的，学到很多。
题解懒得写了，咕了。
Pt T2
题意概括
请用您勤劳的双手自己查看。
题解
nb题。学到很多
首先我们考虑没有开头结尾的按钮限制的情况该怎么做。不难想到一个(DP),(dp[a][b][k])表示(a o b)按得最大按钮(le k)的方案数。
这样显然可以去dp转移
(dp[a][b][i]=dp[a][b][i-1]+sum_{(a,r),(r,b)in E} dp[a][r][i-1] imes dp[r][b][i-1])
(然后发现这是一个矩乘的形式写起来就很方便)
这是一个(Theta(n^3K))的一个预处理。
然后考虑每组询问因为固定了起点终点，就记(f[k][a])表示从s出发，走到a，最大用了k。转移时相当于向量乘矩阵。终点同理，最后卷起来就行。复杂度(Theta(n^2QK))。
另一种可能的做法是将询问拆成新点离线下来用前一个dp去做，复杂度(Theta(n(n+Q)^2K))
Code
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define DEBUG printf("Passing Line %d in function [%s].
",__LINE__,__FUNCTION__)
using namespace std;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ztr;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
x*=f;
}
template<typename T>inline void write(T x){
if(!x)putchar('0');
if(x<0)x=-x,putchar('-');
static int sta[40];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
const int maxn=200007,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
int n,k,Q;
struct Mat{
int a[67][67];
Mat(){memset(a,0,sizeof(a));}
int* operator [](int x){return a[x];}
friend Mat operator *(Mat A,Mat B){
Mat C;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
add(C[i][j],1ll*A[i][k]*B[k][j]%MOD);
return C;
}
void print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<' ';
}
cout<<endl;
}
cout<<endl;
}
}G[67];
struct Vec{
int a[67];
Vec(){memset(a,0,sizeof(a));}
int &operator [](int x){return a[x];}
friend Vec operator *(Vec v,Mat A){
Vec b;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
add(b[j],1ll*A[i][j]*v[i]%MOD);
return b;
}
friend Vec operator +(Vec A,Vec B){
Vec C;
for(int i=1;i<=n;i++)C[i]=mod1(A[i]+B[i]);
return C;
}
}F[67];
inline void init(){
// G[1].print();
for(int i=2;i<=k;i++){
Mat T=G[i-1];
for(int j=1;j<=n;j++)add(T[j][j],1);
G[i]=G[i-1]*T;
// G[i].print();
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(k),read(Q);
for(int i=1;i<=n;i++){
// getchar();
for(int j=1;j<=n;j++)G[1][i][j]=getchar()-'0';
getchar();
}
init();
while(Q--){
int s,t,bs,bt;
read(bs),read(s),read(bt),read(t);
for(int i=1;i<=k;i++)F[i]=Vec();
F[bs][s]=1;
Vec pre=Vec();
for(int i=bs+1;i<=k;i++){
pre=pre+F[i-1]*G[i-1];
F[i]=pre;
}
Vec suf=Vec();
for(int i=k-1;i>=bt;i--){
suf=suf+F[i+1];
F[i]=F[i]+suf*G[i];
}
write(F[bt][t]);putchar('
');
}
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case
好像还有一道t3啥的,整一下
Pt T3
题意概括
给定(n)个区间的并(S=igcuplimits_1^n[l_i,r_i])
,求(a,b,cin S)方案数,使得(a,b,c)两两异或(le K)
(nle20000,K,l,rle10^9)
题解
没啥可以观察到的,硬dp就完事了.
最直观的想法是去trie上dp,有(f_i)表示三个数均在i子树内的方案数。
这时出现了问题，两个走左一个走右没法处理，于是继续暴力设(g_{i,j})表示两个在i子树内，一个在j子树内的方案树，发现(i^j)一定是k的一段前缀，状态数大概是(O(nlog^2n))级别的，没有问题。
同样转移时又出现了问题，一个走左一个走右无法处理，再设一个(h_{i,j})即可。
复杂度3个log左右。
Code
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define DEBUG printf("Passing Line %d in function [%s].
",__LINE__,__FUNCTION__)
// #define int ll
using namespace std;
typedef long long ll;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ztr;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
x*=f;
}
template<typename T>inline void write(T x){
if(!x)putchar('0');
if(x<0)x=-x,putchar('-');
static int sta[40];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
const int maxn=2000007,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
int n,K;
int ch[maxn][2];
int dp1[maxn];
int sz[maxn],dep[maxn];
int p_full[maxn];
map<int ,int > dp2[maxn],dp3[maxn];
int cnt;
int rt;
int C3(int x){return 1ll*x*(x-1)%MOD*(x-2)%MOD*166666668%MOD;}
int C2(int x){return 1ll*x*(x-1)%MOD*500000004%MOD;}
void init(){
for(int i=0;i<=30;i++){
sz[++cnt]=(1<<i);
if(i)ch[cnt][0]=ch[cnt][1]=cnt-1;
// dep[cnt]=i;
p_full[i]=cnt;
}
}
void ins(int &x,int l,int r,int L,int R,int d){
// cout<<" "<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<d<<endl;
if(L<=l&&r<=R){x=d;return;}
// cout<<x<<endl;
if(!x){x=++cnt,dep[x]=d;}
int mid=(l+r)>>1;
if(L<=mid)ins(ch[x][0],l,mid,L,R,d-1);
// cout<<x<<' '<<ch[x][1]<<"OKK"<<endl;
if(R>mid)ins(ch[x][1],mid+1,r,L,R,d-1);
// cout<<x<<' '<<ch[x][1]<<"ALEPF"<<endl;
sz[x]=sz[ch[x][0]]+sz[ch[x][1]];
sz[x]=mod1(sz[x]);
}
int calc3(int x,int y){
if(!x||!y)return 0;
if(!dep[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>>(dep[x]-1)&1)add(dp3[x][y],1ll*sz[ch[x][0]]*sz[ch[y][0]]%MOD);
else add(dp3[x][y],calc3(ch[x][0],ch[y][0]));}
if(ch[x][1]&&ch[y][0])if(K>>(dep[x]-1)&1)add(dp3[x][y],calc3(ch[x][1],ch[y][0]));
if(ch[x][0]&&ch[y][1])if(K>>(dep[x]-1)&1)add(dp3[x][y],calc3(ch[x][0],ch[y][1]));
if(ch[x][1]&&ch[y][1]){
if(K>>(dep[x]-1)&1)add(dp3[x][y],1ll*sz[ch[x][1]]*sz[ch[y][1]]%MOD);
else add(dp3[x][y],calc3(ch[x][1],ch[y][1]));}
return dp3[x][y];
}
int calc2(int x,int y){
if(!x||!y||sz[x]<2)return 0;
if(!dep[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>>(dep[x]-1)&1)add(dp2[x][y],1ll*C2(sz[ch[x][0]])*sz[ch[y][0]]%MOD);
else add(dp2[x][y],calc2(ch[x][0],ch[y][0]));}
if(ch[x][1]&&ch[y][0])if(K>>(dep[x]-1)&1)add(dp2[x][y],calc2(ch[x][1],ch[y][0]));
if(ch[x][0]&&ch[y][1])if(K>>(dep[x]-1)&1)add(dp2[x][y],calc2(ch[x][0],ch[y][1]));
if(ch[x][1]&&ch[y][1]){
if(K>>(dep[x]-1)&1)add(dp2[x][y],1ll*C2(sz[ch[x][1]])*sz[ch[y][1]]%MOD);
else add(dp2[x][y],calc2(ch[x][1],ch[y][1]));}
if(ch[x][0]&&ch[x][1]&&ch[y][0])if(K>>(dep[x]-1)&1)add(dp2[x][y],1ll*sz[ch[x][0]]*calc3(ch[x][1],ch[y][0])%MOD);
if(ch[x][0]&&ch[x][1]&&ch[y][1])if(K>>(dep[x]-1)&1)add(dp2[x][y],1ll*sz[ch[x][1]]*calc3(ch[x][0],ch[y][1])%MOD);
// cout<<x<<' '<<y<<' '<<dp2[x][y]<<endl;
return dp2[x][y];
}
int calc1(int x){
if(!x||sz[x]<3)return 0;
if(!dep[x])return 0;
// cout<<x<<' '<<ch[x][0]<<' '<<ch[x][1]<<endl;
if(~dp1[x])return dp1[x];
// cout<<x<<endl;
dp1[x]=0;
if(ch[x][0])
if(K>>(dep[x]-1)&1)add(dp1[x],C3(sz[ch[x][0]]));
else add(dp1[x],calc1(ch[x][0]));
if(ch[x][1])
if(K>>(dep[x]-1)&1)add(dp1[x],C3(sz[ch[x][1]]));
else add(dp1[x],calc1(ch[x][1]));
if(ch[x][0]&&ch[x][1])
if(K>>(dep[x]-1)&1)
add(dp1[x],calc2(ch[x][0],ch[x][1])),
add(dp1[x],calc2(ch[x][1],ch[x][0]));
// cout<<x<<' '<<dp1[x]<<endl;
return dp1[x];
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(K);
init();
memset(dp1,-1,sizeof(dp1));
// dep[rt]=29;
for(int i=1;i<=n;i++){int l,r;read(l),read(r);ins(rt,0,(1<<30)-1,l,r,30);}
write(calc1(rt));putchar('
');
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case