【题解】AGC047E

题意：有 $2\times 10^5$ 个变量，您可以进行以下两种赋值：

• $a_x\leftarrow a_y+a_z$
• $a_x\leftarrow [a_y<a_z]$

求一串固定的操作序列，使得对任何 $a_0,a_1$，经过这些操作后 $a_2=a_0a_1$。

Subtask 1

$0\le a_0,a_1\le 10$。

考虑维护一个计数器 $c$，每次 $c+1\to c$，然后 $a_2\leftarrow a_1\times [c\le a_0]+a_2$。这样就把乘法操作转化成了有一个数是 $0$ 或者 $1$ 的乘法。

考虑再用相同的暴力来做这个化简后的问题（$[b\ne 0]x+y\to y$），再用计数器 $d$ 维护，假如 $d<x$ 且 $0<a$ 就让 $y$ 加一。即，a[y]+=(a[d]<a[x]&&a[zero]<a[b]，其中 && 运算可以转化为 $[a]+[b]>1$。$1$ 可以用 $0<a_0+a_1$ 得到，$0$ 可以用 $a_x<a_x$ 得到。

于是就用 $O(a_0a_1)$ 次操作解决了这个问题。

Subtask 2

$0\le a_0,a_1\le 10^9$。

首先考虑优化 “有一个数是 $0$ 或 $1$ 的乘法”。这里可以转化成减法，$ab(0\le b\le 1)=\max(a-[b<1]\times 2^{30},0)$。乘二的幂可以用不停 a[x]+=a[x] 实现，减法用倍增实现。枚举 $i$，假如 $y+2^i<x+1$ 则 $ans+2^i\to ans,y+2^i\to y$，结束后 $ans$ 就是差。

然后再用倍增实现普通乘法。利用相同的方法，枚举 $i$，假如初值为 $0$ 的 $p+2^i< x+1$，那么 $p+2^i\to p$，$ans+2^i\times y\to ans$，这样就做完了。

求 $2^ix$ 用去 $O(\log 10^9)$ 次操作，减法的倍增用去 $O(\log 10^9)$ 次左移，求乘法用到 $O(\log 10^9)$ 次判断，总共用了 $O(\log^3 10^9)$ 次操作。

参考实现：https://atcoder.jp/contests/agc047/submissions/15806248