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

· · 题解

原题传送门

思路

我们先假设 a>b>c，由 a \oplus b \oplus c=0 我们可得 a=b \oplus c。又因 a，b，c 可构成三角形，所以 a<b+c，联系 a=b \oplus c，所以 b \oplus c<b+c，那么 b 和 c 在二进制下一定有一位都为 1。所以我们运用状压的思想，将 a>b，b > c 以及 b 和 c 在二进制下一定有一位都为 1 化作三种状态判断即可。

代码

#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int T , dp[60][2][10] , a[60] , n , pos;
inline int dfs(int nows , int zt , bool flag) {
    if(!nows) return zt == 7;
    if(dp[nows][flag][zt] != -1) return dp[nows][flag][zt];
    int maxx = flag ? a[nows] : 1 , tmp = 0;
    if(maxx >= 0) tmp += dfs(nows - 1 , zt , (flag && a[nows] == 0));
    if(maxx >= 0 && (zt & 1) && (zt >> 1 & 1)) tmp += dfs(nows - 1 , zt | 4 , (flag && a[nows] == 0));
    if(maxx == 1) {
        tmp += dfs(nows - 1 , zt | 2 , (flag && a[nows] == 1));
        tmp += dfs(nows - 1 , zt | 1 , (flag && a[nows] == 1));
    }
    dp[nows][flag][zt] = tmp;
    return tmp;
}
inline int work(int x) {
    pos = 0;
    while(x) {
        a[++pos] = x & 1;
        x >>= 1;
    }
    return dfs(pos , 0 , 1) * 3;
}
inline void solve() {
    memset(dp , -1 , sizeof(dp));
    n = read();
    cout << work(n) << endl;
}
signed main(){
    T = read();
    while(T--) solve();
    return 0;
}

注意事项：

这里的 dp 数组一定要开三维，把当前位是否有限制加进去，不然会 T 飞。