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] 整数 提交记录 。

最后此篇关于trick:Trygubnum的文章就讲到这里了,如果你想了解更多关于trick:Trygubnum的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。