数字
NiroBC 姐姐脑洞了两个数字 (x) 和 (y) ，它们满足 (x lor y = T) ，且 (L_x le x le R_x, L_y le y le R_y) ， NiroBC 姐姐想知道 (x land y) 有多少种不同的取值，若有多组 ((x, y)) 的 (x land y) 值相同，则只算一次。
（其中 (lor) 表示按位取或，C/C++中写作|，Pascal中写作or）
（其中 (land) 表示按位取与，C/C++中写作&，Pascal中写作and）
题解
仓鼠《动态规划选讲》。
假设知道(x lor y = T)且(x land y = V)，判断是否可行，可以做一个数位DP。
(f[i][a][b][c][d])表示考虑到第(i)位，(x)与(L_x)和(R_x)的关系，(y)与(L_y)和(R_y)的关系，这种情况下是否可行。
然后写一个外层DP，把所有内层结果压起来就可以了。
(F[i][S])表示DP到第(i)位，DP状态为(S)的(V)有多少个。
转移枚举(V)的第(i)位是什么，时间复杂度(O(2^{16}log T))。
// f[i][01][01][01][01]
int F[61][1<<16];
IN int state(int a,int b,int c,int d){
return a|b<<1|c<<2|d<<3;
}
signed main(){
int T=read<int>();
int Lx=read<int>(),Rx=read<int>();
int Ly=read<int>(),Ry=read<int>();
F[60][1<<state(1,1,1,1)]=1;
for(int i=59;i>=0;--i){
int t=T>>i&1;
int lx=Lx>>i&1,rx=Rx>>i&1;
int ly=Ly>>i&1,ry=Ry>>i&1;
for(int s=0;s<1<<16;++s){
if(!F[i+1][s]) continue;
for(int q:{0,1}){
int news=0;
for(int a:{0,1})for(int b:{0,1})for(int c:{0,1})for(int d:{0,1}){
if(~s>>state(a,b,c,d)&1) continue;
for(int x:{0,1})for(int y:{0,1}){
if((x|y)!=t or (x&y)!=q) continue;
if(a and x<lx) continue;
if(b and x>rx) continue;
if(c and y<ly) continue;
if(d and y>ry) continue;
news|=1<<state(a and x==lx,b and x==rx,c and y==ly,d and y==ry);
}
}
F[i][news]+=F[i+1][s];
}
}
}
int ans=0;
for(int s=1;s<1<<16;++s) ans+=F[0][s];
printf("%lld
",ans);
return 0;
}