题目描述

求(x,y)的对数满足x∈[0,a],y∈[0,b],x⊕y=0且|x-y|<=m

题解

一种比较sb的做法是考虑x-y的借位，根据借位以及差值进行转移

还有一种比较正常的做法，假设一开始x=0,y=n，那么就需要把y的某一些1移到x上，也就是对于(x-y)加上2^(i+1)

设加的数之和为s，那么需要保证|s-n|<=m，也就是n-m<=s<=n+m

注意是当n的第i位为1时才可以加上2^(i+1)，把上界右移一位后就变成加上2^i

设f[i][0/1][0/1][0/1]，表示当前到第i位，x、y、s是否顶住上界

枚举第i位的xy所选，使得x[i]^y[i]=n[i]且新的s不会越界即可

code

sb版

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
using namespace std;

int a[60];
int b[60];
int x[60];
int y[60];
long long f[61][2][2][2][2];
int T,i,j,k,l,I,J,K,L,p,q,P,Q,fs,ll;
long long n,m,A,B,ans;

int swap(int &x,int &y)
{
    int z=x;
    x=y;
    y=z;
}

void work()
{
    memset(f,0,sizeof(f));
    f[60][0][0][0][0]=1;
    fd(i,60,1)
    {
        I=i-1;

        fo(j,0,1)
        {
            fo(k,0,1)
            {
                fo(p,0,1)
                {
                    fo(q,0,1)
                    if (f[i][j][k][p][q])
                    {
                        if (!a[I])
                        {
                            if (j && !b[I]) continue;

                            fo(l,0,1)
                            if ((p || x[I]>=l) && (q || y[I]>=l))
                            {
                                if (!j && b[I]>0) K=1; else K=k;
                                if (x[I]>l) P=1; else P=p;
                                if (y[I]>l) Q=1; else Q=q;

                                f[I][j][K][P][Q]+=f[i][j][k][p][q];
                            }
                        }
                        else
                        {
                            if (I==fs) ll=1;
                            else ll=0;

                            fo(l,ll,1)
                            if ((p || x[I]>=l) && (q || y[I]>=(1-l)))
                            {
                                if (!l)
                                {
                                    if (!j)
                                    J=0,K=1;
                                    else
                                    {
                                        if (b[I])
                                        J=0,K=k;
                                        else
                                        J=1,K=k;
                                    }
                                }
                                else
                                {
                                    if (j && !b[I]) continue;

                                    if (k)
                                    J=0,K=1;
                                    else
                                    {
                                        if (!b[I])
                                        {
                                            if (j)
                                            continue;
                                            else
                                            J=1,K=0;
                                        }
                                        else
                                        {
                                            if (j)
                                            continue;
                                            else
                                            J=0,K=0;
                                        }
                                    }
                                }
                                if (x[I]>l) P=1; else P=p;
                                if (y[I]>(1-l)) Q=1; else Q=q;

                                f[I][J][K][P][Q]+=f[i][j][k][p][q];
                            }
                        }
                    }
                }
            }
        }
    }

    fo(k,0,1)
    {
        fo(p,0,1)
        {
            fo(q,0,1)
            ans+=f[0][0][k][p][q];
        }
    }
}

int main()
{
    scanf("%d",&T);
    for (;T;--T)
    {
        scanf("%lld%lld%lld%lld",&A,&B,&n,&m);

        fs=-1;

        fo(i,0,59)
        {
            a[i]=n&1;
            n>>=1;

            if (a[i])
            fs=i;
        }

        if (fs==-1)
        {
            printf("%lld\n",min(A,B)+1);
            continue;
        }

        fo(i,0,59) b[i]=m&1,m>>=1;
        fo(i,0,59) x[i]=A&1,A>>=1;
        fo(i,0,59) y[i]=B&1,B>>=1;

        ans=0;
        work();

        fo(i,0,59)
        swap(x[i],y[i]);

        work();

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

正常版

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;

int a[61];
int x[61];
int y[61];
int z[61];
long long f[61][2][2][2];
int T,i,j,k,l,I,J,K,L,s,S,X,Y,X2,Y2;
long long N,M,A,B,s1;

void turn(int *a,long long s)
{
    int i;

    fo(i,1,60)
    a[i]=s%2,s/=2;
}

long long work(long long t)
{
    long long ans=0;

    if (t>=0)
    {
        t/=2;
        turn(a,t);
    }
    else
    return 0;

    memset(f,0,sizeof(f));
    f[60][0][0][0]=1;

    fd(i,60,1)
    {
        I=i-1;

        fo(j,0,1)
        {
            fo(k,0,1)
            {
                fo(l,0,1)
                if (f[i][j][k][l])
                {
                    if (j) X2=1; else X2=x[i];
                    if (k) Y2=1; else Y2=y[i];

                    fo(X,0,X2)
                    {
                        if (X<x[i]) J=1; else J=j;

                        fo(Y,0,Y2)
                        if ((X^Y)==z[i] && !(!l && X && !Y && !a[i]))
                        {
                            if (Y<y[i]) K=1; else K=k;
                            if ((X && !Y)<a[i]) L=1; else L=l;

                            f[I][J][K][L]+=f[i][j][k][l];
                        }
                    }
                }
            }
        }
    }

    fo(j,0,1)
    {
        fo(k,0,1)
        {
            fo(l,0,1)
            ans+=f[0][j][k][l];
        }
    }

    return ans;
}

int main()
{
    scanf("%d",&T);
    for (;T;--T)
    {
        scanf("%lld%lld%lld%lld",&A,&B,&N,&M);
        turn(x,A);
        turn(y,B);
        turn(z,N);

        printf("%lld\n",work(N+M)-work(N-M-1));
    }
}