题意:有 2×105 个变量,您可以进行以下两种赋值:
- ax←ay+az
- ax←[ay<az]
求一串固定的操作序列,使得对任何 a0,a1,经过这些操作后 a2=a0a1。
Subtask 1
0≤a0,a1≤10。
考虑维护一个计数器 c,每次 c+1→c,然后 a2←a1×[c≤a0]+a2。这样就把乘法操作转化成了有一个数是 0 或者 1 的乘法。
考虑再用相同的暴力来做这个化简后的问题([b≠0]x+y→y),再用计数器 d 维护,假如 d<x 且 0<a 就让 y 加一。即,a[y]+=(a[d]<a[x]&&a[zero]<a[b]
,其中 && 运算可以转化为 [a]+[b]>1。1 可以用 0<a0+a1 得到,0 可以用 ax<ax 得到。
于是就用 O(a0a1) 次操作解决了这个问题。
Subtask 2
0≤a0,a1≤109。
首先考虑优化 “有一个数是 0 或 1 的乘法”。这里可以转化成减法,ab(0≤b≤1)=max(a−[b<1]×230,0)。乘二的幂可以用不停 a[x]+=a[x]
实现,减法用倍增实现。枚举 i,假如 y+2i<x+1 则 ans+2i→ans,y+2i→y,结束后 ans 就是差。
然后再用倍增实现普通乘法。利用相同的方法,枚举 i,假如初值为 0 的 p+2i<x+1,那么 p+2i→p,ans+2i×y→ans,这样就做完了。
求 2ix 用去 O(log109) 次操作,减法的倍增用去 O(log109) 次左移,求乘法用到 O(log109) 次判断,总共用了 O(log3109) 次操作。
参考实现:https://atcoder.jp/contests/agc047/submissions/15806248
0 条评论