$CF809C\ Find\ a\ car$ 数位$dp$
正解:数位$dp$
解题报告:
然后因为没有翻译所以先放个翻译$QAQ$
有一个无穷大的矩阵,第$i$行第$j$列的数是$(i-1)\ xor\ (j-1)+1$,有$q$次询问,每次询问一个矩形内$(x_{1},y_{1})(x_{2},y_{2})$小于等于$k$的数的和
好像是考试题,,,?学长出的$QwQ$?
然后考虑怎么做趴$QwQ$,发现这个式子其实要拆成两个部分?一个是$\sum (i-1)\ xor\ (j-1)$,一个是$\sum 1$,所以考虑拆成两个部分?一个为和一个为方案数$QwQ$
其实和与方案数的求法差不多,,,我就以和为$eg$港下怎么做嗷$QwQ$
其实是类似普通的数位$dp$的,设$f_{i,0/1,0/1,0/1}$表示考虑到第$i$位,$x$是否到达上限,$y$是否到达上限,$x\ xor\ y$是否到达上限.这么解释着可能有点儿空,,,,详细解释下$QwQ$
$f_{i,p,q,r}$,$i$表示二进制拆分后从高位到低位考虑到$x\ xor\ y$的第$i$位了,$p$表示二进制拆分后行号$x$是否是顶着$x_{1}$/$x_{2}$的,$q$表示二进制拆分后列号$y$是否是顶着$y_{1}$/$y_{2}$的,$r$表示二进制拆分后$x\ xor\ y$的值是否是顶着$k$的,然后转移下就好.这样解释下大概就能$get$了?发现其实和普通的数位$dp$也差不多,只不过平常的数位$dp$是十进制分解,这里因为涉及二进制运算所以就二进制分解掉了$QwQ$
然后转移也和普通的数位$dp$差不多?就如果顶着上线继续转移,否则随便搞
$over$?
对了这题不用$dfs$,直接$for$循环那种转移简洁明了$w$
恩留一个坑,就其实题目最开始给定的是说$(x,y)$这个格子的值是$mex_{i=1,j=1}^{x-1,y-1}dat_{i,j}$,但是因为我并不会证为什么它就等于$(x-1)\ xor\ (y-1)$,,,所以咕了$QwQ$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ri register int
#define rb register int
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int mod=1e9+7,N=35;
int K,f[N][2][2][2],g[N][2][2][2];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il int solv(ri x,ri y)
{
memset(f,0,sizeof(f));memset(g,0,sizeof(g));f[31][0][0][0]=1;if(x<0 || y<0)return 0;
my(i,30,0)
rp(p,0,1)
rp(q,0,1)
rp(r,0,1)
if(f[i+1][p][q][r])
rp(j,0,1)
rp(k,0,1)
{
if(!p && j && !(x&(1<<i)))continue;
if(!q && k && !(y&(1<<i)))continue;
if(!r && (j^k) && !(K&(1<<i)))continue;
ri tmpp=p,tmpq=q,tmpr=r;
if(!j && (x&(1<<i)))tmpp|=1;
if(!k && (y&(1<<i)))tmpq|=1;
if(!(j^k) && (K&(1<<i)))tmpr|=1;
(f[i][tmpp][tmpq][tmpr]+=f[i+1][p][q][r])%=mod;
(g[i][tmpp][tmpq][tmpr]+=g[i+1][p][q][r])%=mod;
if(j^k)(g[i][tmpp][tmpq][tmpr]+=1ll*(1<<i)*f[i+1][p][q][r]%mod)%=mod;
}
ri ret=0;rp(i,0,1)rp(j,0,1)rp(k,0,1)(ret+=g[0][i][j][k])%=mod,(ret+=f[0][i][j][k])%=mod;return ret;
}
main()
{
//freopen("809c.in","r",stdin);freopen("809c.out","w",stdout);
ri T=read();
while(T--)
{
ri x_1=read()-1,y_1=read()-1,x_2=read()-1,y_2=read()-1;K=read()-1;
printf("%d\n",(solv(x_2,y_2)+solv(x_1-1,y_1-1)+mod+mod-solv(x_2,y_1-1)-solv(x_1-1,y_2))%mod);
}
return 0;
}