题意:有 $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

分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code