一种计算2的极大幂的有效方法

Question

我正在解决一个问题，这个问题需要我计算一个集合中所有可能子集的平方和。我被要求返回这个和，模10^9+7

我已经理解了其中的逻辑。我只需要对平方求和，然后将结果乘以2^N-1，其中N是集合的大小。

但问题是N可以大到10^5，为此，我得到了一个整数溢出。我研究了快速的模幂运算，但我仍然可以在哪里存储像2^100000这样大的数据？我可以在计算2的幂时使用模数来减小数字吗？这不会改变最终的值吗？

如果有人能告诉我如何获取它或阅读什么，那将是非常有帮助的。

Answer 1

如果你用2^something_big取模，这只意味着你不需要输出something_big以外的位。例如x%power(2,10) == x%(1<<10) == x&(1<<10 - 1) == x&1023。

因此，在你的例子中，问题是在计算模数之前计算实际值，同时记住你只需要99999位。所有更高的位都要去掉(如果我正确理解了你的前提，应该不会影响结果)。

顺便说一句。存储99999位是可行的。它只有13kB。