[Codeforces-div.1 809C] Find a car

试题分析

莫名结论：\(a_{i,j}=(i-1) xor (j-1) +1\)

然后分成\(i\space xor\space j\)和 \(1\)分别数位dp计算。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

#define LL long long

inline LL read(){

    LL x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const LL MAXN = 100010;

const LL INF = 2147483600;

const LL Mod = 1e9+7;

LL Q,x1,x2,Y1,y2,k;

LL dp[41][5][5][5],f[41][5][5][5];

LL cnt[5],str[5][MAXN+1];

inline void split(LL x,LL k){

    for(LL i=1;i<=cnt[k];i++) str[k][i]=0;

    cnt[k]=0; while(x){str[k][++cnt[k]]=x&1; x>>=1;}

    return ;

}

inline LL calc(LL x,LL y,LL K){

    --x,--y; if(x<0||y<0) return 0;

    for(int i=33;i>=0;i--)

        for(int j=0;j<2;j++)

            for(int k=0;k<2;k++)

                for(int l=0;l<2;l++)

                    dp[i][j][k][l]=f[i][j][k][l]=0;

    split(x,1); split(y,2); split(K,3);

    f[32][1][1][1]=1;

    for(LL i=32;i>=1;i--){

        for(LL t1=0;t1<2;t1++)

            for(LL t2=0;t2<2;t2++)

                for(LL t3=0;t3<2;t3++){

                    if(!f[i][t1][t2][t3]) continue;

                    //cout<<i<<"="<<t1<<" "<<t2<<" "<<t3<<":"<<f[i][t1][t2][t3]<<" "<<str[1][i]<<" "<<str[2][i]<<endl;

                    for(LL a=0;a<=(t1?str[1][i]:1);a++){

                        for(LL b=0;b<=(t2?str[2][i]:1);b++){

                            if(t1&&a>str[1][i]) continue;

                            if(t2&&b>str[2][i]) continue;

                            if(t3&&(a^b)>str[3][i]) continue;

                            LL nxt1=(t1?(a==str[1][i]):0);

                            LL nxt2=(t2?(b==str[2][i]):0);

                            LL nxt3=(t3?((a^b)==str[3][i]):0);

                            //cout<<"check:"<<i<<" "<<nxt1<<" "<<nxt2<<" "<<nxt3<<":";

                            f[i-1][nxt1][nxt2][nxt3]+=f[i][t1][t2][t3]; f[i-1][nxt1][nxt2][nxt3]%=Mod;

                            dp[i-1][nxt1][nxt2][nxt3]+=(dp[i][t1][t2][t3]+1LL*f[i][t1][t2][t3]*((a^b)<<(i-1))%Mod)%Mod;

                            dp[i-1][nxt1][nxt2][nxt3]%=Mod;

                            //cout<<" "<<dp[i-1][nxt1][nxt2][nxt3]<<" "<<dp[i-1][nxt1][nxt2][nxt3]<<endl;

                        }

                    }

                }

    } LL s=0;

    for(LL i=0;i<2;i++){

        for(LL j=0;j<2;j++){

            for(LL k=0;k<2;k++)

                s+=(dp[0][i][j][k]+f[0][i][j][k])%Mod,s%=Mod;

        }

    } return s%Mod;

}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    Q=read();

    while(Q--){

        x1=read(),Y1=read(),x2=read(),y2=read(),k=read(); LL ans=0;

        k--; if(k==-1) {puts("0"); continue;}

        ans=(ans+calc(x2,y2,k)%Mod)%Mod;

        //system("pause");

        ans=(ans+calc(x1-1,Y1-1,k)%Mod)%Mod;

        ans=(ans-calc(x2,Y1-1,k)+Mod)%Mod;

        ans=(ans-calc(x1-1,y2,k)+Mod)%Mod;

        printf("%lld\n",ans);

    }

    return 0;

}