（从洛谷博客搬过来的）
学校比赛的时候考了这道题，我当然是一分没得。
这是一道好构造题。
先不说正解，我看别的题解都没有说怎么拿部分分，但是如果赛时不会正解，那么拿部分分就是很必要的一件事了，所以我在这里说一说。想直接看正解的可以跳过部分分讲解。
注：下文中的 \(“⊕”\) 指的是异或运算。
算法一 暴力枚举 \((30pts)\)
我们考虑在什么情况下能够合成一。因为加和运算是始终使数增加的，所以是用异或运算来合成 \(1\)，并且当且仅当一对相邻的奇数偶数时才能异或出来 \(1\)。
也就是在类似这种情况下再进行一步异或即可合成 \(1\)：
00010110101
00010110100
可以称此局面为出解局面。
考虑如何枚举。设 \(S\) 为已经合成的数的集合，那么可以枚举每一个 \(S\) 里的元素然后对 \(S\) 里的元素全部进行相加和异或操作，得到的新数再次扔到 \(S\) 里，继续枚举，直到出现出解局面为止。
关于如何判断出解局面是否出现，可以用一个 \(map\) 记录出现了哪些数，然后在合成了新的数 \(w\) 时 \(\text{check}\) 一下 \(w+1\text{、}w-1\) 有没有出现过，出现的话了判断一下异或出来是否为 \(1\) ，如果为 \(1\) 则输出答案。
算法二 随机化 \((40 \sim 96pts)\)
随机化还是比较好用的，我们学校 \(\text{OJ}\) 上有人 \(\text{40pts}\)，也有人 \(\text{96pts}\)，得分高低主要看你写的丑不丑以及你是怎样随机化的了。
分数相对低一点的做法( 一般在 \(\text{80pts}\) 以下)，可在已经 \(S\) 里随机选一个出来，然后对 \(S\) 里的元素全部进行相加和异或操作，把新的数再扔到 \(S\) 里，如此往复直到达到出解局面。当然了如果你写的足够好也可以获得接近 \(\text{90pts}\) 的高分。
对于写数字次数不超过 \(10^5\) 这个限制，显然我们在得到答案的路上是有很多无用的数被合成的，对存答案的结构体一趟 \(dfs\) 把这些数从答案中删掉即可。也可以 \(dfs\) 查找答案是怎样被合成的。
分数较高一点的做法( \(\text{80pts}\) 以上)是 \(\text{Delov}\) 大佬想出来的，考虑样例是怎样构造的：\(+ ⊕ + + ⊕\)，两个样例都是这样，这似乎昭示了什么规律。大胆猜测这种构造方式可以构造出答案，那么就按照他这个操作去进行随机化，也就是循环这个操作数列，然后每次在 \(S\) 里随机选一个数出来对 \(S\) 中的数进行当前循环到的操作( \(+\) 或者 \(⊕\) )，相应判断是否达到出解局面。可以获得 \(\text{85pts}\) 左右的高分。
提高出解率的方法是构造如下的操作数列并执行：
\[+++\ ...++\ ⊕\ ++++... \]也就是随机在操作数列里插入一些 \(⊕\)，使得 \(+\) 的操作次数要较多于 \(⊕\)。这样目前测得最高可以获得 \(\text{93pts}\)。
还有一种可以获得最高 \(\text{96pts}\) 的随机化，涉及到 \(\text{exgcd}\)，这里不再赘述，因为并不是正解。
算法三 构造 \((100pts)\)
正解其实挺简单的。考虑如何将数字 \(9\) 合成为1：
9: 0000 1001
因为题目保证给出的 \(x\) 是奇数，所以 \(x\) 的最低位一定是 \(1\)。
考虑如何运用这个性质。观察到对于相同的数 \(w\) 进行加和运算就是使 \(w\) 乘上一个 \(2\)，也就等同于 \(w\) 左移一位，那么就可以通过左移来用 \(x\) 最低位的 \(1\) 去消去较高位的 \(1\)，不妨每次去消掉 \(x\) 最高位的 \(1\)。考虑如何实现。
首先另取一个数 \(y=x\)，令 \(y\) 最低位的 \(1\) 与 \(x\) 最高位的 \(1\) 对齐：
x: 0000 1001
y: 0100 1000
之后令 \(x ⊕ y\) 得到 \(z\)：
x: 0000 1001
y: 0100 1000
z: 0100 0001
再令 \(y + z\) 得到 \(a\)：
x: 0000 1001
y: 0100 1000
z: 0100 0001
a: 1000 1001
再令 \(a ⊕ (y<<1) ⊕ x\) 得到 \(b\)：
x: 0000 1001
y: 0100 1000
z: 0100 0001
a: 1000 1001
1001 0000 ←(y<<1)
b: 0001 0000
这时候发现 \(b\) 只剩下一位了，但并不是 \(x\) 的最高位；不过我们可以用 \(b\) 依次把 \(y\) 较高位的 \(1\) 消掉，直到 \(y\) 变成 \(x\) 的最高位，再用 \(y\) 去消掉 \(x\) 的最高位即可。
如此循环消掉 \(x\) 最高位直到 \(x=1\) 即可。
代码实现：
#include <iostream>
#include <bitset>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define N 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
struct Answer{int opt; long long x, y;};
long long x, y, z, a, tmp, plc, anscnt, b, c, d;
struct Answer ans[N];
#define lowbit(x) ((x) & (-(x)))
inline void Xiao(){
tmp = x; y = x;
while (tmp != 0)// 取出来x的最高位
plc = lowbit(tmp), tmp ^= plc;
while (lowbit(y) != plc)
{ans[++ anscnt] = (Answer){1, y, y}; y <<= 1;}// 得到y
// 对齐之后另其与x异或
ans[++ anscnt] = (Answer){2, x, y};
z = x ^ y;
// 另z与y相加得到a
ans[++ anscnt] = (Answer){1, y, z};
a = y + z;
// y左移
ans[++ anscnt] = (Answer){1, y, y};
d = y + y;
// a与y与x异或
ans[++ anscnt] = (Answer){2, a, d};
ans[++ anscnt] = (Answer){2, a^d, x};
b = a ^ d ^ x;
// 用b去消y
c = b>>1;
while (y != c){
if ((y & b) == b)
{ans[++ anscnt] = (Answer){2, y, b}, y = y ^ b;}
ans[++ anscnt] = (Answer){1, b, b}; b <<= 1;
}
// 此时剩下的y就是x最高位了
ans[++ anscnt] = (Answer){2, y, x};
x = x ^ y;
}
inline void work(){
cin >> x;
while (x != 1)
Xiao();
cout << anscnt << '\n';
for (re i = 1 ; i <= anscnt ; ++ i){
cout << ans[i].x;
cout << ((ans[i].opt == 1) ? (" + ") : (" ^ "));
cout << ans[i].y << '\n';
}
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}