其实这题的某个位置((i,j))的数是((i-1)mathrm{xor}(j-1)+1)
首先一个矩形的答案可以拆成((x2,y2)-(x1-1,y2)-(x2,y1-1)+(x1-1,y1-1))
然后这里有三个限制(ile x,jle y,i mathrm{xor} jle k),可以考虑dp之类的.我们从高位往低位做,设(f_{i,j,k,l})表示第(i)位,现在的(i,j,i mathrm{xor} j)是否达到上界的权值和,转移枚举下一位是什么,如果当前这个数在上界,可以让他继续卡着上界,也可以不卡上界;否则可以随便放
注意那个(+1),我们另外设(g_{i,j,k,l})表示方案数,答案为所有权值和+方案数
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
using namespace std;
const int N=3e5+10,mod=1e9+7;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int f[2][2][2][2],g[2][2][2][2];
void ad(int &x,int y){x+=y,x-=(x>=mod)?mod:0;}
LL sov(int mx,int my,int mk)
{
if(mx<0||my<0) return 0;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
int nw=1,la=0;
g[0][1][1][1]=1;
for(int i=30;~i;--i)
{
int x=mx>>i&1,y=my>>i&1,kk=mk>>i&1;
for(int j=0;j<=1;++j)
for(int k=0;k<=1;++k)
for(int l=0;l<=1;++l)
{
if(!g[la][j][k][l]) continue;
for(int xx=0;xx<=(x|(!j));++xx)
for(int yy=0;yy<=(y|(!k));++yy)
if((xx^yy)<=kk||!l)
{
ad(f[nw][j&(xx==x)][k&(yy==y)][l&((xx^yy)==kk)],(f[la][j][k][l]+1ll*g[la][j][k][l]*((xx^yy)<<i)%mod)%mod);
ad(g[nw][j&(xx==x)][k&(yy==y)][l&((xx^yy)==kk)],g[la][j][k][l]);
}
f[la][j][k][l]=g[la][j][k][l]=0;
}
nw=!nw,la=!la;
}
int ans=0;
for(int j=0;j<=1;++j)
for(int k=0;k<=1;++k)
for(int l=0;l<=1;++l)
ad(ans,(f[la][j][k][l]+g[la][j][k][l])%mod);
return ans;
}
int main()
{
//aha
int T=rd();
while(T--)
{
int ax=rd()-1,ay=rd()-1,bx=rd()-1,by=rd()-1,k=rd()-1;
printf("%lld
",(sov(bx,by,k)-sov(ax-1,by,k)-sov(bx,ay-1,k)+sov(ax-1,ay-1,k)+mod+mod)%mod);
}
return 0;
}