自动搬运

查看原文

来自洛谷，原作者为

	chroneZ **

搬运于2025-08-24 22:42:15，当前版本为作者最后更新于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();
}