证明
给定正整数 $n$，满足 $n = 2^{d_1} + 2^{d_2} + 2^{d_3} + 2^{d_4}$，请构造 $n$ 的一个最短的加法链 (Addition chain)。
输入包含多组数据。第一行包含一个正整数 $T$ ($T \leq 500$)，表示数据组数。
对于每组数据，共一行，包含四个非负整数 $d_1, d_2, d_3, d_4$ ($d_i \leq 20$)，表示正整数 $n = 2^{d_1} + 2^{d_2} + 2^{d_3} + 2^{d_4}$。
对于每组数据，若 $n$ 的最短加法链为 $1 = a_0 < a_1 < \cdots < a_r = n$，则第一行输出一个正整数 $r$。
接下来 $r$ 行，第 $i$ ($1 \leq i \leq r$) 行输出三个整数 $a_{r-i+1}, a_j, a_k$ ($0 \leq j, k < r - i + 1; a_{r-i+1} = a_j + a_k$)，描述 $a_{r-i+1}$ 是如何产生的。
你需要保证你的加法链是所有加法链中最短的。如果有多个最短的加法链，输出任意一个均可。
用 $l \left( n \right)$ 表示 $n$ 的加法链的最短长度，$\nu \left( n \right)$ 表示 $n$ 的二进制表示下 $1$ 的个数 (即 $\operatorname{popcount} \left( n \right)$)，$\lambda \left( n \right) = \left \lfloor \log_2 n \right \rfloor$。
显然，由快速幂可知 $$ l \left( n \right) \leq \lambda \left( n \right) + \nu \left( n \right) - 1 \tag 1 \label 1 $$
(ps: 但等号不总是成立，如对 $n = 15$，$\left[ 1, 2, 3, 6, 9, 15 \right]$ 就是一个稍短的加法链)
事实上，对于一般的 $n$，求解 $l \left( n \right)$ 是一个十分困难的事情，目前学术界没有一个较好的方法。
不过题目中的 $n$ 显然是有性质的。因为 $n$ 等于四个 $2$ 的方幂之和，因此不难发现 $\nu \left( n \right) \leq 4$。因此我们只需要对 $\nu \left( n \right) \leq 4$ 的 $n$ 进行讨论即可。而 $\nu \left( n \right) \leq 4$ 的加法链的情形其实是已经解决的。
(ps: 事实上，即便对于 $\nu \left( n \right) = 5$，学术界都没有解决)
首先，一个显然的性质是 $a_i \leq 2^i$，因此 $n = a_r \leq 2^r \Rightarrow r \geq \left \lceil \log_2 n \right \rceil$，即 $$ \color {fuchsia} {l \left( n \right) \geq \left \lceil \log_2 n \right \rceil} \tag 2 \label 2 $$
于是，当 $\nu \left( n \right) = 1$，即 $n$ 是 $2$ 的方幂时，$l \left( n \right) = \log_2 n$，构造就是 $1, 2, 2^2, 2^3, \cdots, 2^r$。
对 $\nu \left( n \right) \geq 2$ 的情形，可知 $n$ 不是 $2$ 的方幂，从而 $\log_2 n \notin \mathbb Z$，从而 $\left \lceil \log_2 n \right \rceil = \left \lfloor \log_2 n \right \rfloor + 1 = \lambda \left( n \right) + 1$，从而 $\eqref 2$ 可加强为 $$ \color {fuchsia} {l \left( n \right) \geq \lambda \left( n \right) + 1} \tag 3 \label 3 $$
于是，结合 $\eqref 1 \eqref 3$ 可知，当 $\nu \left( n \right) = 2$ 时，$l \left( n \right) = \lambda \left( n \right) + 1$。
对于 $\nu \left( n \right) = 3$ 和 $\nu \left( n \right) = 4$ 的情形稍微有些复杂，但是还是可以讨论清楚的。
首先是 $\nu \left( n \right) = 3$ 的情形，这时我们有 $\color {orange} {l \left( n \right) = \lambda \left( n \right) + 2}$，证明如下 (下图来自《The Art of Computer Programming, Vol 2: Semi-numerical Algorithms》第 427 ~ 429 页)：
对于 $\nu \left( n \right) = 4$ 的情形，$l \left( n \right)$ 可以取到 $\lambda \left( n \right) + 2$ 或 $\lambda \left( n \right) + 3$。具体的分析与证明同样还是参见《The Art of Computer Programming, Vol 2: Semi-numerical Algorithms》第 429 ~ 430 页：
于是大力分类讨论即可，时间复杂度 $O \left( \log n \right)$。
#include <bits/stdc++.h>
#define EB emplace_back
#define ctz __builtin_ctz
#define popc __builtin_popcount
using std::cin;
using std::cout;
typedef std::vector <int> vector;
namespace addition_chain {
vector construct(int n) {
int i, j, a, b, c, d; vector ret;
if (popc(n) < 3) {
for (i = 1; i < n; i <<= 1) ret.EB(i);
return ret.EB(n), ret;
}
if (popc(n) == 3) {
for (i = 1; i < n; i <<= 1) ret.EB(i);
return ret.EB(n & (n - 1)), ret.EB(n), ret;
}
assert(popc(n) == 4),
i = n, a = ctz(i),
i &= i - 1, b = ctz(i),
i &= i - 1, c = ctz(i),
i &= i - 1, d = ctz(i);
if (a + 1 == b && b + 1 == c && c + 5 == d) { // 135 * 2^n
ret = {1, 2, 3, 6, 12, 15, 30, 60, 120};
for (i = 135; i <= n; i <<= 1) ret.EB(i);
return ret;
}
if (a + d == b + c) {
for (i = 0; i <= b; ++i) ret.EB(1 << i);
for (i = a, j = b; i <= c; ++i, ++j) ret.EB(1 << i | 1 << j);
return ret.EB(n), ret;
}
if (a + d == b + c + 1) {
for (i = 0; i <= b; ++i) ret.EB(1 << i);
ret.EB(1 << a | 1 << b);
for (i = a, j = b + 1; i <= c; ++i, ++j) ret.EB(1 << i | 1 << j);
return ret.EB(n), ret;
}
if (a + 1 == b && c + 3 == d) {
for (i = 0; i <= c + 1; ++i) ret.EB(1 << i);
return ret.EB(3 << c), ret.EB(3 << c | 1 << a), ret.EB(6 << c | 2 << a), ret.EB(n), ret;
}
for (i = 1; i < n; i <<= 1) ret.EB(i);
return ret.EB(1 << c | 1 << d), ret.EB(n & (n - 1)), ret.EB(n), ret;
}
}
void work() {
int i, j, k, l;
cin >> i >> j >> k >> l;
vector ch(addition_chain::construct((1 << i) + (1 << j) + (1 << k) + (1 << l)));
l = ch.size(), cout << l - 1 << '\n';
for (i = l - 1; i; --i)
for (j = 0; j < i; ++j) {
for (k = j; k < i; ++k)
if (ch[i] == ch[j] + ch[k]) {cout << ch[i] << ' ' << ch[j] << ' ' << ch[k] << '\n'; break;}
if (k < i) break;
}
}
int main() {
int T;
std::ios::sync_with_stdio(false), cin.tie(NULL);
for (cin >> T; T; --T) work();
return 0;
}
坑1：$n = 2^{d_1} + 2^{d_2} + 2^{d_3} + 2^{d_4}$ 并不说明 $\nu \left( n \right) = 4$ (因为 $d_i$ 可能相等)。
坑2：输出时别忘记是 "倒着" 输出的。