Processing math: 100%

题意:有 2×105 个变量,您可以进行以下两种赋值:

  • axay+az
  • ax[ay<az]

求一串固定的操作序列,使得对任何 a0,a1,经过这些操作后 a2=a0a1

Subtask 1

0a0,a110

考虑维护一个计数器 c,每次 c+1c,然后 a2a1×[ca0]+a2。这样就把乘法操作转化成了有一个数是 0 或者 1 的乘法。

考虑再用相同的暴力来做这个化简后的问题([b0]x+yy),再用计数器 d 维护,假如 d<x0<a 就让 y 加一。即,a[y]+=(a[d]<a[x]&&a[zero]<a[b],其中 && 运算可以转化为 [a]+[b]>11 可以用 0<a0+a1 得到,0 可以用 ax<ax 得到。

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

Subtask 2

0a0,a1109

首先考虑优化 “有一个数是 01 的乘法”。这里可以转化成减法,ab(0b1)=max(a[b<1]×230,0)。乘二的幂可以用不停 a[x]+=a[x] 实现,减法用倍增实现。枚举 i,假如 y+2i<x+1ans+2ians,y+2iy,结束后 ans 就是差。

然后再用倍增实现普通乘法。利用相同的方法,枚举 i,假如初值为 0p+2i<x+1,那么 p+2ipans+2i×yans,这样就做完了。

2ix 用去 O(log109) 次操作,减法的倍增用去 O(log109) 次左移,求乘法用到 O(log109) 次判断,总共用了 O(log3109) 次操作。

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

分类: 文章

0 条评论

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注