HDU 5598：GTW likes czf 敲了一天的数位DP

GTW likes czf

 

 Accepts: 6

 

 Submissions: 29

 Time Limit: 4000/2000 MS (Java/Others)

 

 Memory Limit: 131072/131072 K (Java/Others)

问题描述

从前，有两个人名叫GTW，DSY。一天，他们为了争夺DSY的妹子CZF，决定进行一次决斗。首先，CZF会给出一个区间$l,l+1,l+2......r$，和两个数$G,T$。现在，CZF会在$G,T$两个数中随机一个数$X$，在区间$l,r$中随机一个数Y,进行一种特殊的运算@。CZF想要快速知道有多少数字可能会是答案。
然而GTW并不会做这道题，但是为了赢得CZF，他就来寻求你的帮助。
由于答案可能会很大，所以把最终的答案模1000000007。
我们规定运算X @ Y =((X and Y) or Y) xor X.

输入描述

第1行 一个整数$Test$，表示有$Test$组数据。$(Test\le 10000)$
第2行到第$Test+1$行，每行4个整数，$l,r,G,T$ (1\leq l,r,G,T\leq 10^{18},l\leq r1≤l,r,G,T≤10​18​​,l≤r)

输出描述

共$Test$行，每行一个数字，表示答案。

输入样例

1
2 4 2 4

输出样例

4

Hint

2 xor 2=0,2 xor 3=1,2 xor 4=6
4 xor 2=6,4 xor 3=7,4 xor 4=0
总共有4个数字是 0 1 6 7

官方题解：首先会发现x @ y=$xxory$，(ps:出题人很良心，在样例解释里暴露了这一事实) 并且一个数字和其它若干个不同的数字$xor$的结果肯定是互不相同的，所以最后的答案就是$(r-l+1)\ast 2-$重复数字。

那么如何求重复数字呢。显然需要满足$gxorx=txory$，$x$和$y$是我们从区间$[l,r]$中挑出来的数字，通过移项，就变成了$gxort=xxory$，所以我们要求$[l,r]$中有多少对$x,y$异或等于$gxort$这个东西显然可以数位dp。

所以这个题目就是要求从0到m里面 与从0到n里面有多少对元素的 异或 等于给定的值。

用dp[i][x][y]表示进行到第i位合法的数量，x=1时表示a还是原数，即最大值不变。y=1时表示b仍是原数，即最大值不变，剩下的就是不断“释放”的一个过程。

代码：

#pragma warning(disable:4996)  
#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
#include <string>  
#include <cstring>  
using namespace std;
typedef long long ll;

const int mod = 1000000007;

ll x;
ll le, ri, G, T;

int nn[65], mm[65], xx[65];
ll dp[65][2][2];

void input()
{
    scanf("%lld%lld%lld%lld", &le, &ri, &G, &T);
}

ll cal(ll n, ll m)
{
    memset(dp, 0, sizeof(dp));

    int i;
    for (i = 63; i >= 0; i--)
    {
        nn[i] = (n >> i) & 1;
        mm[i] = (m >> i) & 1;
        xx[i] = (x >> i) & 1;
    }
    int flag = 0;//找首位的标记
    for (i = 62; i >= 0; i--)
    {
        if (flag == 0)
        {
            if (!nn[i] && !mm[i] && !xx[i])//0 0 0
                continue;
            else if (!nn[i] && !mm[i] && xx[i])//0 0 1
                return 0;
            else if (!nn[i] && mm[i] && !xx[i])//0 1 0
            {
                //因为是首位，只能是0 0 0，不可能是1 1 0
                dp[i][1][0] = 1;
            }
            else if (!nn[i] && mm[i] && xx[i])//0 1 1
            {
                //因为是首位，只能是0 1 1，不可能是1 0 1
                dp[i][1][1] = 1;
            }
            else if (nn[i] && !mm[i] && !xx[i])//1 0 0
            {
                //因为是首位，只能是0 0 0，不可能是1 1 1
                dp[i][0][1] = 1;
            }
            else if (nn[i] && !mm[i] && xx[i])//1 0 1
            {
                //因为是首位，只能是1 0 1，不可能是0 1 1
                dp[i][1][1] = 1;
            }
            else if (nn[i] && mm[i] && !xx[i])//1 1 0
            {
                //这时可以是 1 1 0，也可以是0 0 0
                dp[i][1][1] = 1;
                dp[i][0][0] = 1;
            }
            else if (nn[i] && mm[i] && xx[i])//1 1 1
            {
                //这时可以是 1 0 1，也可以是0 1 1
                dp[i][1][0] = 1;
                dp[i][0][1] = 1;
            }
            flag = 1;
        }
        else
        {
            if (!nn[i] && !mm[i] && !xx[i])//0 0 0
            {
                dp[i][1][1] = dp[i + 1][1][1];
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

            }
            else if (!nn[i] && !mm[i] && xx[i])//0 0 1
            {
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;
            }
            else if (!nn[i] && mm[i] && !xx[i])//0 1 0
            {
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

                //1 1 0的情况
                dp[i][0][0] += dp[i + 1][0][1];

                //0 0 0的情况
                dp[i][1][0] += dp[i + 1][1][1];
            }
            else if (!nn[i] && mm[i] && xx[i])//0 1 1
            {
                dp[i][1][1] = dp[i + 1][1][1];
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

                // 1 0 1 
                dp[i][0][0] += dp[i + 1][0][1];
            }
            else if (nn[i] && !mm[i] && !xx[i])//1 0 0
            {
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

                //0 0 0的情况把n这部分释放了出来
                dp[i][0][0] += dp[i + 1][1][0];
                dp[i][0][1] += dp[i + 1][1][1];

            }
            else if (nn[i] && !mm[i] && xx[i])//1 0 1
            {
                dp[i][1][1] = dp[i + 1][1][1];
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

                // 0 1 1
                dp[i][0][0] += dp[i + 1][1][0];
            }
            else if (nn[i] && mm[i] && !xx[i])//1 1 0
            {
                dp[i][1][1] = dp[i + 1][1][1];
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

                //0 0 0
                dp[i][0][0] += (dp[i + 1][1][0] + dp[i + 1][0][1] + dp[i + 1][1][1]);
            }
            else if (nn[i] && mm[i] && xx[i])//1 1 1
            {
                dp[i][0][1] = dp[i + 1][0][1];
                dp[i][1][0] = dp[i + 1][1][0];
                dp[i][0][0] = dp[i + 1][0][0] * 2;

                //0 1 1
                dp[i][0][1] += dp[i + 1][1][1];
                dp[i][0][0] += dp[i + 1][1][0];

                //1 0 1
                dp[i][1][0] += dp[i + 1][1][1];
                dp[i][0][0] += dp[i + 1][0][1];
            }
        }
    }
    return (dp[0][0][0] + dp[0][1][0] + dp[0][0][1] + dp[0][1][1])%mod;
}

void solve()
{
    x = G^T;
    ll ans = ((ri - le + 1) * 2) % mod;
    ans = (ans - (cal(ri, ri) - cal(le - 1, ri) * 2 + cal(le-1, le-1)) % mod + mod) % mod;

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

int main()
{
    //freopen("i.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);

    int t;
    scanf("%d", &t);

    while (t--)
    {
        input();
        solve();
    }

    //system("pause");
    return 0;
}