hdu 6899 Xor

Xor

传送门

题意：对于x属于[1,a]，y属于[1,b]。|x-y| <= k，x xor y <= w的x，y的对数。

分析：数位dp，首先是这个绝对值条件要去掉，变成两个条件。y-x+k >= 0 && x-y+k>=0。我们现在按位考虑这个两个限制，会发现这个位(把x-y+k当成一个数)上，会填{-1,0,1,2}，会发现其实前面的和对后面的影响只有为数不多的几种情况。前面小于-1，这种后面怎么填都不合法，直接白给。-1，0，大于等于1后面怎么都合法，我们设计状态只考虑这三种情况就可以了。其次按位考虑xor的限制，这个其实非常好处理，只需要限制一下x xor y的值就行了，毕竟w这一位取1，x xor y取0之后，后面就随便取了，只需要多一个限制就行了。

细节：如果只开f [N] [3] [3]，时间不够跑(嘤，多开几个维度才够。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 35;

LL f[N][3][3][2][2][2];

LL a, b, n, m;

/*
    有借位的数位dp，首先应该将条件转化一下：
    第一：有二进制的限制
    第二：y-x+m>=0&&x-y+m>=0
*/

LL dfs(int dep, int v1, int v2, int flag1, int flag2, int flag3){
    v1=min(v1,1);v2=min(v2,1);

    if(v1<-1||v2<-1)return 0;

    if(dep==-1){
        if(v1>=0&&v2>=0)return 1;
        else return 0;
    }

    if(~f[dep][v1+1][v2+1][flag1][flag2][flag3])return f[dep][v1+1][v2+1][flag1][flag2][flag3];

    int up1=flag1?(a>>dep&1):1;
    int up2=flag2?(b>>dep&1):1;

    LL& res=f[dep][v1+1][v2+1][flag1][flag2][flag3];
    res=0;
    for(int i=0;i<=up1;++i){
        for(int j=0;j<=up2;++j){
            if(flag3&&((i^j)>((m>>dep)&1)))continue;
            int tp1=v1*2+i-j+((n>>dep)&1);
            int tp2=v2*2+j-i+((n>>dep)&1);
            res+=dfs(dep-1,tp1,tp2,flag1&&(i==up1),flag2&&(j==up2),flag3&&((i^j)==(m>>dep&1)));
        }
    }

    return res;
}

int main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%lld%lld%lld%lld",&a,&b,&n,&m);
        memset(f,-1,sizeof f);
        printf("%lld
",dfs(30,0,0,1,1,1));
    }
    return 0;
}