trick大意

我对于这个trick的理解为:支持位运算的高精度
维护一个以 \(b\)为基数的大数 \(N\),并支持以下功能:

  • 给定(可能是负)整数 \(|x|, |y| \leqslant n\),将 \(x b^y\)加到 \(N\)
  • \(N \geqslant 0\)时,给定\(k\),打印\(N\)的第\(k\)位数字(指以\(b\)为基底意义下的)。
  • 检查\(N\)是正值、负值还是等于\(0\)

操作 \(O(\log n)\)均摊时间复杂度和 \(O(q)\)内存。并且只需要map进行实现,相比于线段树等数据结构维护非常的好写。

例题及实现 : [NOI2017] 整数

题意简述 : 一个整数\(x\),进行\(n\)次操作,分为两种:

  • \(x\) 加上整数 \(a\cdot 2^b\),其中 \(a\) 为一个整数,\(b\) 为一个非负整数

  • 询问 \(x\) 在用二进制表示时,位权为 \(2^k\) 的位的值(即这一位上的 \(1\) 代表 \(2^k\)

保证在任何时候,\(x\geqslant 0\)

  • 对于所有测试点,满足 \(|a| \leqslant 10^9\)
  • 对于所有测试点,满足 \(0 \leqslant b, k \leqslant 30n\)
  • 对于所有测试点,满足 \(n \leqslant 1000000\)

这里我们的基底为\(2^{30}\),感性理解一下:把\(x\)的二进制表示分为若干段,每一段长是\(30\)位,这样每次我们只需要改动最多两段,分别对这两段将原数字位运算为相应位后直接加到数中,多于\(2 ^ {30}\)的进行进位操作。

发现其实很像一个\(2^{30}\)进位制,这也是以\(b\)为基底的真正含义

关于均摊时间复杂度

其实我不是很能证明,但是再次感性理解,就是假设一些段内的数为\([2^{30} – 1,2^{30} – 1,2^{30} – 1,2^{30} – 1…]\) 即对应二进制内全为\(1\)
显然加一次,他就会往后进很多位花大量时间,虽然这一次花了很多时间,但是呢,需要进位的次数其实是很少的,而不需要进位的时候,直接加又很快,这样下来我们的均摊时间就不是那么慢了。

  • 具体证明看这里

代码

先咕,急的看参考资料。

习题

  • [NOI2017] 整数

  • 1817E – Half-sum

  • 1810F – M tree

  • 102354E -Decimal Expansion

参考资料

如果英语还不错,可以直接看原CF博客:
Big integers with negative digits: The Trygub numbers

CF原作者的[NOI2017] 整数提交记录