P8766 [蓝桥杯 2021 国 AB] 异或三角 - 题解

chroneZ · 2023-03-22 01:57:27 · 题解

考虑数位 dp。下文记 x_i 表示 x 在二进制意义下的第 i 位。

考虑枚举 a 作为最大值，则原题可以视作求满足一些限制的有序数对 (a, b, c) 的数量。

• 对于限制 a > b，等价于从高位向低位均有 b_i = a_i，直到首次出现 (a_i, b_i) = (1, 0)
• 对于 a > c 同上。
• 对于限制 a < b + c，由原限制 2 可知 a = b \oplus c，b \oplus c < b + c 当且仅当 \exists (b_i, c_i) = (1, 1)。
• 对于限制 a = b \oplus c，在转移过程中只考虑 (a_i, b_i, c_i) = (0, 1, 1), (0, 0, 0), (1, 0, 1), (1, 1, 0) 四种可能情形即可。

只有满足所有限制的数对会对答案产生贡献。我们用一个二进制数压缩前三个限制的当前状态，记忆化搜索实现 dp，具体细节见代码。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 32;

int a[N]; i64 f[N][8][2];
i64 dfs(int cur, int state, bool fulc){
    if(cur < 0) return state == 7;  // 同时满足所有限制
    if(~f[cur][state][fulc]) return f[cur][state][fulc];
    int dig = fulc ? a[cur] : 1; i64 res = 0;
    for(int k = 0; k <= dig; k++){
        if(k == 0){
            int b = state & 1, c = state >> 1 & 1;
            res += dfs(cur - 1, state, fulc && (k == dig)); // (a_i, b_i, c_i) = (0, 0, 0)
            if(b == 1 && c == 1) res += dfs(cur - 1, state | 4, fulc && (k == dig)); // (a_i, b_i, c_i) = (0, 1, 1)
        }
        if(k == 1){
            res += dfs(cur - 1, state | 1, fulc && (k == dig)); // (a_i, b_i, c_i) = (1, 0, 1)
            res += dfs(cur - 1, state | 2, fulc && (k == dig)); // (a_i, b_i, c_i) = (1, 1, 0)
        }
    }
    return f[cur][state][fulc] = res;
}
void solve(){
    memset(f, -1, sizeof f);
    int n; cin >> n;
    int L = -1;
    while(n) a[++L] = n % 2, n /= 2;
    cout << dfs(L, 0, 1) * 3 << "\n";
}
int main(){
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while(T--)
        solve();
}