2019牛客第七场H题 (Pair) 数位DP

题意：给三个数a,b,c，求pair<x,y> ，其中 ，并且满足下列至少一条条件：

题解：由于两个数都是位运算，考虑数位dp。又因为两个情况都没有包含等号，所以考虑都不满足这两个条件的pair，即 。然后注意我们求的pair是不包含0的，所以直接数位dp的答案需要减去满足上述条件含有0的pair。

然后就是一个常规的数位dp。

#include <algorithm>
#include <cstring>
#include <iostream>
#define int long long
using namespace std;
int diga[32], digb[32], digc[32];
int dp[32][2][2][2][2];

int go(int s, bool upa, bool upb, bool upand, bool upxor)
{
    if (s == -1)
    {
        return 1;
    }
    if (dp[s][upa][upb][upand][upxor] != -1)
    {
        return dp[s][upa][upb][upand][upxor];
    }
    int topa = upa ? diga[s] : 1;
    int topb = upb ? digb[s] : 1;
    int topc_xor = upxor ? digc[s] : 0;
    int topc_and = upand ? digc[s] : 1;
    int res = 0;
    for (int a = 0; a <= topa; a++)
    {
        for (int b = 0; b <= topb; b++)
        {
            if ((a & b) > topc_and)
                continue;
            if ((a ^ b) < topc_xor)
                continue;
            res += go(s - 1, upa && a == topa, upb && b == topb, upand && ((a & b) == topc_and), upxor && ((a ^ b) == topc_xor));
        }
    }
    return dp[s][upa][upb][upand][upxor] = res;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    int _;
    cin >> _;
    while (_--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        for (int i = 0; i < 32; i++)
        {
            diga[i] = (a >> i) & 1;
            digb[i] = (b >> i) & 1;
            digc[i] = (c >> i) & 1;
        }
        memset(dp, -1, sizeof(dp));
        int ans = go(31, 1, 1, 1, 1);
        ans -= max(0ll, a - c + 1) + max(0ll, b - c + 1);
        cout << a * b - ans << endl;
    }
}