CF1338C Perfect Triples 题解

题意：

通过如下方式构造一个无穷数列 $S$：

选择一个字典序最小的有序三元组 $(a,b,c)$ ，且满足 $a,b,c \notin S~, a \oplus b\oplus c=0$。

将 $a,b,c$ 依次加入数列 $S$。

$T(T \le 10^5)$ 组询问，每次给出一个数 $n(1\le n\le 10^{16})$ ，求数列 $S$ 的第 $n$ 项。

打表找规律题，打表程序：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

struct node { int a, b, c; };
bool operator<(node x, node y)
{
	if(x.a != y.a) return x.a < y.a;
	else if(x.b != y.b) return x.b < y.b;
	return x.c < y.c;
}
vector<node> vec; char used[1111];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	// freopen("check.in","r",stdin);
	freopen("check.out","w",stdout);
	for(int i = 1; i <= 1000; i++)
		for(int j = i + 1; j <= 1000; j++)
			for(int k = j + 1; k <= 1000; k++)
				if((i ^ j ^ k) == 0 && !used[i] && !used[j] && !used[k])
					vec.push_back({i, j, k}), used[i] = used[j] = used[k] = 1;
	sort(vec.begin(), vec.end());
	for(auto i : vec) cout << i.a << ' ' << i.b << ' ' << i.c << '\n';
	return 0;
}

表（部分）：

可以发现，答案被分成了若干块，每一块的 $a$ 都是 $2^k$ 到 $2^{k+1}-1$ 的连续整数

$b$ 的规律有一点不太容易看得出来，我们可以这么看

16 32 48 // 0
17 34 51 // 2
18 35 49 // 3   // 0
19 33 50 // 1

20 40 60
21 42 63
22 43 61        // 2
23 41 62

24 44 52
25 46 55
26 47 53        // 3
27 45 54

28 36 56
29 38 59
30 39 57        // 1
31 37 58

于是我们可以通过递归构造 $b$ ，而 $c=a\oplus b$ 可以很容易得到。实现的细节比较繁琐。

时间复杂度 $\mathcal{O}(T\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int calc(int x, int y)
{
    if(x == 1) return 1;
    int t = x / 4;
    if(y <= t) return calc(t, y);
    else if(y <= 2 * t) return calc(t, y - t) + 2 * t;
    else if(y <= 3 * t) return calc(t, y - 2 * t) + 3 * t;
    else return calc(t, y - 3 * t) + t;
}
void solve()
{
    int n, tmp; cin >> n; tmp = n % 3;
    n = (n + 2) / 3; int pos = 0, cnt = 0;
    while(pos + (1ll << cnt) < n) { pos += (1ll << cnt); cnt += 2; }
    int res = 3 * pos;
    if(tmp == 1) cout << res + (n - pos) << '\n';
    else if(tmp == 2) cout << res + (1ll << cnt) + calc(1ll << cnt, n - pos) << '\n';
    else cout << ((res + (n - pos)) ^ (res + (1ll << cnt) + calc(1ll << cnt, n - pos))) << '\n';

}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}