E. Perfect Triples

题目链接

题目概要：

有一个无限大的数组(s)。(开始为空)
每次找到字典序最小的三个数((a,b,c))满足：

• (aoplus boplus c=0).
• (a,b,c otin s).
  (t)次询问，每次问数组第(n)项是多少。

思路：

打表后我们发现，三元组的第一项始终是 (4^x)后一段连续的数。这样我们尝试在二进制下两位两位的转移
（也就是四进制，为了使异或看起来方便我们这样描述）：
每两位可以取的数值是(00，01，10，11)。
首先假设已经用完了(1 o 4^n-1)的数，现在考虑(4^n o 4^{n+1}-1)。
要得到 (a<b<c) ，最高的两位只能是(01，10，11)，也就是说(a,b,c)最高的两位互不相同。
现在前两位已经知道了，我们继续往下看。
我们先把样例给出的几项（二进制）用下表的形式展示：

我们大胆猜测，（以两位为单位）在四进制下，所有的数值都满足以上条件。

• 两位的情况下((a,b,c))只有(1，2，3)，显然满足。
• 假设(2k)位的情况下(a,b,c)都满足，验证(2k+2)位：
  我们先把这(2k)位左移两位（设其中任意一对数值是(pa,pb,pc)，显然(pa oplus pb=pc)），在字典序最小的情况下我们首先考虑(a)：
  (00)：显然(pa+00,pb+00,pc+00)成立。
  (01)：对于(b)，(00，01)都不成立（(b,c)出现重复），此时应为 (pa+01,pb+10,pc+11)。
  ...
  剩下的手推便会发现的确满足上表。

这样我们只要确定第(n)个数所属的三元组((a,b,c）)的(a)即可确定这个值。

代码：

#include "iostream"
#include "stdio.h"
#include "string.h"
#include "algorithm"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1e6+5;
const ll mod=998244353;
const double eps=1e-5;
//const double pi=acos(-1);

#define ls p<<1
#define rs p<<1|1
ll f[3][4]={{0,3,1,2},{},{0,2,3,1}};
void solve(ll x,int y)
{
    if(y==1)
    {
        printf("%lld
",x);
        return;
    }
    ll ans=0,p=1;
    while(x)
    {
        ans=ans+f[y][x%4]*p;
        x>>=2;
        p<<=2;
    }
    printf("%lld
",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    ll n;
    cin>>_;
    while(_--)
    {
        cin>>n;
        ll j=1,a;
        while(j<=n) j<<=2;
        j>>=2;
        if(j+2>=n) a=j;
        else a=j+(n-j)/3;
        solve(a,n%3);
    }
    return 0;
}