异或三角形（数位dp）-Toy模板网

这篇具有很好参考价值的文章主要介绍了异或三角形（数位dp）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

异或三角形

[Link](异或三角 - 蓝桥云课 (lanqiao.cn))

参考：2021蓝桥杯国赛-J异或三角形-数位dp_塔子哥来了的博客-CSDN博客_蓝桥杯数位dp

题意

给定 $T$ 个数 $n_1,n_2,...,n_T$ ，对每个 $n_i$ 请求出有多少组 $a, b, c$ 满足：

$1\le a,b,c\le n_i$
$a\oplus b\oplus c =0$
长度为 $a, b, c$ 的三条边能组成一个三角形

思路

数位 $d p$

涉及 $\oplus$ 一般从二进制看比较好，对于 $a\oplus b\oplus c=0$ 这个限制我们发现 $a, b, c$ 三个数一定是不同的，三个边组成一个三角形即保证 $max(a,b,c)\times 2<a+b+c$ ，由于不好确定哪个边是最大的，这里我们假设 $a$ 是最长边，答案就是 $a$ 为最长的情况 $\times 3$ 即可。

已知 $a$ 为最长边，我们可以按二进制从高到底枚举 $a, b, c$ 每一位选什么，由于 $a\oplus b\oplus c=0 \to c=a\oplus b$ ，因此我们只需枚举 $a, b$ 每一位选择什么即可， $c$ 可由 $a, b$ 的情况推出，下面将我们题目的限制转化为对应二进制选法的限制（假设每一位的选法为 $a_i,b_i)$ 即 $a, b$ 这一位是 $0$ 还是 $1$ ）：

$a > b$ : 由于 $a$ 是最大的，因此我们要保证 $(1, 0)$ 出现在 $(0, 1)$ 前面
$a > c$ : $c_i=a_i\oplus b_i$ ，我们要保证 $(1, 1)$ 出现在 $(0, 1)$ 前面，因为 $(1, 1)$ 的时候 $c_i=0$ 这样 $a > c$ 就成立, $(0, 1)$ 的时候 $c_i=1,a_i=0$ 如果先出现 $a < c$ 就与假设相反了
$1\le a\le n$ ：枚举的时候注意上界即可
$a < b + c$ ： $a=b\oplus c\to b\oplus c < b + c$ ，即存在 $(0, 1)$ ，因为这时 $a_i=0,b_i=1,c_i=1$ ，对于第 $i$ 位 $b_i\oplus c_i=0$ ，因此一定小于 $b + c$

综上所述：我们只需满足 $(0, 1)$ 出现在 $(1, 0), (1, 1)$ 后面，且 $(0, 1), (1, 0), (11)$ 均出现即可。

对于 $(a, b)$ 的三种情况用二进制来状压一下， $1 : (0, 1), 2 : (1, 0), 3 : (1, 1)$ ，考虑数位 $d p$ : $f [u] [l i m i t] [s t a t e] :$ 前 $u$ 位，是否有限制，且当前状态为 $s t a t e$ 的方案数，记忆化搜索写一下就可以了。

数位 $d p$ 的一般写法可以参考一下大佬的讲解：[Link](数位DP笔记(DFS做法) - AcWing)

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int m, k;
LL n;
int a[N], cnt;
LL f[31][2][8];
LL dfs(int u, int limit, int state) {
	if (!u) return state == 7;
	LL &t = f[u][limit][state];
	if (~t) return t;	
	LL res = 0;
	int up = limit ? a[u] : 1;

	for (int i = 0; i <= up; i ++) 
		if (!i) {
			res += dfs(u - 1, limit && i == up, state);
			if (state >= 6) 
			res += dfs(u - 1, limit && i == up, state | 1);
		}
		else {
			res += dfs(u - 1, limit && i == up, state | 2);
			res += dfs(u - 1, limit && i == up, state | 4);
		}
	
	return t = res; 	
}
LL dp(LL x) {
	cnt = 0;
	memset(f, -1, sizeof f);	
	while (x) {
		a[++cnt] = x & 1;
		x >>= 1;		
	}	
	return dfs(cnt, 1, 0) * 3;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T -- ) {		
		cin >> n;
		cout << dp(n) << '\n';
	}
	return 0;
}