Description
按照如下方式构造一个无穷数列 (S)。选取一个字典序最小的三元组 ((a,b,c)) 满足 (a,b,c otin S),并且 (a oplus b oplus c = 0),将 (a,b,c) 依次加入到序列 (S) 末尾。给定 (n) 求数列的第 (n) 项。
Solution
观察到,三个成组,答案可以分为若干段,第 (i ge 0) 的长度为 (4^{i-1})。
设当前组的开头数字为 (B),则 (B sim B+4^{i-1}-1) 都是分配给 (a) 的,(B sim B+4^{i-1} sim B + 2 imes 4^{i-1} - 1) 都是分配给 (b) 的,(c) 可以偷懒用 (a,b) 求出。
为了求 (b),可以将当前区间分成四段,分别取第 (1,3,4,2) 小的 (B sim B+4^{i-1} sim B + 2 imes 4^{i-1} - 1) 划分成四段后的子区间,然后递归分治下去,直到求出。
其实 (c) 也可以用类似 (b) 的方法直接求出,只要把顺序换成 (1,4,2,3) 即可。
当然也可以不递归,直接写入二进制各位的值。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
const int k[3][4]={{0,1,2,3},{0,2,3,1},{0,3,1,2}};
void solve()
{
int n;
cin>>n;
int group=(n-1)/3-1, type=(n-1)%3;
int ans=0,bas=1;
while(group>=0)
{
ans+=bas*k[type][group%4];
group=group/4-1;
bas*=4;
}
cout<<ans+bas*(type+1)<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
}