trick : Trygub num
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\)。
显然加一次，他就会往后进很多位花大量时间，虽然这一次花了很多时间，但是呢，需要进位的次数其实是很少的，而不需要进位的时候，直接加又很快，这样下来我们的均摊时间就不是那么慢了。
- 具体证明看这里
代码
先咕，急的看参考资料。
习题
参考资料
如果英语还不错，可以直接看原CF博客:
Big integers with negative digits: The Trygub numbers
CF原作者的[NOI2017] 整数提交记录