闲话

很水的构造题，但是没有场切（太蒟蒻力）。

正文

solution

一次在 CF 上看到了 Constructive Algorithms 的 tag，于是在 oiwiki 上了解了一下。

很容易发现这题满足构造题的特点：输入规模大（$n \in [1,1e5]$)，答案存在某种规律（手推一下 $n \in [1,10]$ 的答案就可以发现）。

所以这是道构造题，然后呢？

特殊性质

可以观察下特殊性质，正解往往可以从特殊性质上推出，这题也不例外。

这题的特殊性质是 $\forall n , \exists k \ge 0 ,k \in \mathbb N ,n = 2^k -1$，翻译过来就是对于所有的 $n$ 存在自然数 $k$ 使得 $n = 2^k -1$。

有什么用呢？

首先，题面出现了按位与，考虑位运算。在二进制中，第 $i$ 位对应 $2^i$（设最低位为第 $0$ 位），正如十进制中第 $i$ 位对应 $10^i$。而 $2^k$ 正对应一个第 $k$ 位为 $1$，其余位为 $0$ 的二进制数。

那么 $2^k -1$ 呢？

由于二进制里是逢二进一，所以一个前 $k-1$ 位为 $1$ 的二进制数加 $1$ 后会怎么样呢？首先，第 $0$ 位加 $1$ 变 $2$，逢二进一，向第 $1$ 位进 $1$，自己变 $0$；然后第 $1$ 位加 $1$ 变 $2$，逢二进一，向第 $2$ 位进 $1$，自己变 $0$；此后同理，第 $k-1$ 位加 $1$ 变 $2$，逢二进一，向第 $k$ 位进 $1$，自己变 $0$，最终得到第 $k$ 位为 $1$，其余为 $0$ 的二进制数，即 $2^k$。所以反过来，$2^k-1$ 就是一个前 $k-1$ 位为 $1$ 的二进制数。

有什么启示呢？

不难发现，对于 $[1,2^k-1]$ 中的任何一个数 $num$，$2^k-1$ 减去 $num$ 与 $num$ 按位与一定为 $0$（$1$ 相互错开），那么对于特殊性质，一种可行的构造就是：将前一半的数与 $n$ 减去它分在一组，因为 $[0,2^k-1]$ 中有 $2^k$ 个数，为 $2$ 的倍数，所以一定恰好分完。

正解

受特殊性质启发，我们可以先求出第一个大于等于 $n$ 的数 $Maxn$，满足 $\exists k \ge 0 ,k \in \mathbb N , Maxn = 2^k -1$。然后将 $[ Maxn - n,n]$ 中的数按上述方法分组（前一半的数与 $Maxn$ 减去它分一组），会发现剩下的 $[0,Maxn - n -1]$ 是完全相同的子问题，递归求解即可。

code

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,bmi,bmi2,fma")
#include<bits/stdc++.h>
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar()  (p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,t;
void solve(int x){
    if(x==0){
        printf("1 0\n");
        return;
    }
    if(x<0){
        return;
    }
    int tmp=log2(x);
    int maxn=(1<<(tmp+1))-1;
    for(int i=maxn-x;i<=maxn/2;i++){
        printf("2 %d %d\n",i,maxn-i);
    }
    solve(maxn-x-1);
}
signed main(){
  //freopen(".in","r",stdin);
  //freopen(".out","w",stdout);
    t=read();
    while(t--){
        n=read();
        write(n/2+1);
        putchar('\n');
        solve(n);
    }
    return 0;
}

还是很水的喵～