题意
爱莉给了你一个非负整数 nnn，你需要把 0,1,2,…,n0, 1, 2, \dots, n0,1,2,…,n 划分成若干组，满足每一组的按位与为 000。
划分的组不需要相邻。
你需要最大化划分组数并给出方案。
1≤T≤6001 \le T \le 6001≤T≤600，0≤n≤1050 \le n \le 10^50≤n≤105，保证单个测试点内 nnn 的和不超过 2×1052 \times 10^52×105。
思路
闲着没事去看了两眼，题目越简洁，看着越吓人，做法越要思考。实在没想到这个只有黄的 T3，不过挺好玩的。
由打表样例可见，每一组似乎都不超过 2 个。不妨就构造两个两个一组的答案，可能会多出一个 000，理论上可以得到 ⌈n+12⌉\left \lceil \dfrac{n+1}{2} \right \rceil⌈2n+1⌉ 组。
考虑怎么样得到两个数与起来为 000，需要二进制每一位要么相反要么均为 000。
假若有一个数 2x=(100...000)22^x=(100...000)_22x=(100...000)2，其中 000 有 xxx 个，另一个数 2x−1=(11...111)22^x-1=(11...111)_22x−1=(11...111)2，其中 111 也有 xxx 个；这二者与起来为 000，而若前者一直 +1+1+1，后者一直 −1-1−1，两个数按位与起来总是为 000。为什么呢？每次 +1+1+1 或者 −1-1−1，要么只改变末尾，要么发生进位改变高位——进位可能改变连续的高位。但是各位在初始状态总是相反，所以两个数同时改变各位依旧相反。
那么可以这样构造：找到小于 nnn 的最大 2x2^x2x，将 n∼2xn\sim 2^xn∼2x 加进队列，然后从 2x2^x2x 和 2x−12^x-12x−1 依次向大和向小枚举配对；设后者配对到 pospospos，当前者配对到 nnn 就停下，然后向队列中增补 2x−1∼pos−12^{x-1}\sim pos-12x−1∼pos−1，下一轮继续遍历到 pos−1pos-1pos−1 ……——如果还没配对到 nnn，pospospos 就到了 2x−12^{x-1}2x−1 怎么办？此时 2x−1>pos−12^{x-1}>pos-12x−1>pos−1，可以直接忽略进队列的操作，继续把队列里剩下的元素配对玩再说，根据上面的结论来看这时可行的。
最后看队列有没有剩下的，如果 nnn 为奇数队列中将会剩下一个，此时让其和 000 配对；否则 000 自成一组。
讲得有点口胡了。具体细节见代码。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T,n;
ll p2[22];
void init()
{
p2[0]=1;
for(int i=1;i<=20;i++)
p2[i]=p2[i-1]*2;
}
queue<ll>q;
void clean()
{
while(!q.empty())q.pop();
}
int main()
{
scanf("%lld",&T);
init();
while(T--)
{
clean();
scanf("%lld",&n);
if(n==0)
{
puts("1");
puts("1 0");
continue;
}
printf("%lld\n",(n+2)/2);
ll x=upper_bound(p2+1,p2+21,n)-p2-1;
for(int i=p2[x];i<=n;i++)
q.push(i);
for(int i=x-1;i>=0;i--)
{
ll pos=p2[i+1]-1;
while(!q.empty()&&pos>=p2[i])
{
printf("2 %lld %lld\n",pos,q.front());
pos--;
q.pop();
}
for(int j=p2[i];j<=pos;j++)
q.push(j);
}
if(!q.empty())printf("2 0 %lld\n",q.front());
else puts("1 0");
}
return 0;
}