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) 加上整数 (acdot 2^b)，其中 (a) 为一个整数，(b) 为一个非负整数
-
询问 (x) 在用二进制表示时，位权为 (2^k) 的位的值（即这一位上的 (1) 代表 (2^k)）
保证在任何时候，(xgeqslant 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)。
显然加一次，他就会往后进很多位花大量时间，虽然这一次花了很多时间，但是呢，需要进位的次数其实是很少的，而不需要进位的时候，直接加又很快，这样下来我们的均摊时间就不是那么慢了。
- 具体证明看这里
代码
先咕，急的看参考资料。
习题
参考资料
如果英语还不错，可以直接看原CF博客:
Big integers with negative digits: The Trygub numbers
CF原作者的[NOI2017] 整数提交记录
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
