題意：給三個數(shù)a,b,c檬某，求pair<x,y> 撬腾，其中 ，并且滿足下列至少一條條件：
題解：由于兩個數(shù)都是位運(yùn)算恢恼，考慮數(shù)位dp民傻。又因為兩個情況都沒有包含等號，所以考慮都不滿足這兩個條件的pair厅瞎，即 饰潜。然后注意我們求的pair是不包含0的，所以直接數(shù)位dp的答案需要減去滿足上述條件含有0的pair和簸。
然后就是一個常規(guī)的數(shù)位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;
}
}
