You need to enable JavaScript to run this app. CSES位串问题:位移位实现失效原因及逐次乘2取模正确性疑问
优惠活动
大模型
产品
解决方案
定价
更多

CSES位串问题:位移位实现失效原因及逐次乘2取模正确性疑问

移位实现失效的根本原因

你写的移位实现从根上就存在逻辑硬伤,和unsigned long long的数值范围能不能存下2^n没有直接关系:

  • 所有C++内置整数类型的位宽是有固定上限的,主流平台下unsigned long long固定为64位,哪怕是部分编译器扩展支持的128位无符号整数,也仅能覆盖到2^128的移位范围,远达不到题目n最大1e6的需求。
  • C++标准明确规定,当移位操作的移位位数大于等于被移位对象的位宽时,属于未定义行为。比如当n=65时,对64位的1ULL做左移65位,绝大多数编译器的实际实现会把移位位数对64取模,等效为做左移1位,最终得到2,和预期的2^65结果完全偏差。

这种思路下,根本走不到“数值溢出存不下”的环节,移位操作本身在n>64时就已经计算出错误值了,后续对这个错误值做取模自然不可能得到正确结果。

逐次取模的计算逻辑正确性

你对逐次取模的疑问核心是:为什么不需要先算出完整的2^n全量值,只靠每轮乘2后取余得到的结果就是最终的正确值?
这个逻辑的成立完全基于取模运算的基本数学性质,不存在任何简化或近似:

  • 对任意正整数m,两个整数的乘积对m取余,等价于两个数分别对m取余后再相乘、再对m取余,也就是公式:
    (a * b) mod m = [(a mod m) * (b mod m)] mod m

顺着这个性质做递推:
我们设递推的每轮结果ans_k等于2^k mod MOD,要计算的最终结果就是ans_n = 2^n mod MOD。
根据上面的性质:
2^k = 2^(k-1) * 2,因此2^k mod MOD = [ (2^(k-1) mod MOD) * 2 ] mod MOD
也就是ans_k = (ans_{k-1} * 2) mod MOD,和循环里写的计算逻辑完全一致。

举个直观的验证例子,取MOD=7,计算2^4 mod7的正确结果是16 mod7=2:

  • 初始ans_0 = 2^0 mod7 =1
  • ans_1 = (1*2) mod7 =2,和2^1=2 mod7结果一致
  • ans_2 = (2*2) mod7 =4,和2^2=4 mod7结果一致
  • ans_3 = (4*2) mod7 =8 mod7=1,和2^3=8 mod7结果一致
  • ans_4 = (1*2) mod7 =2,和2^4=16 mod7结果一致

哪怕中间某轮计算的乘积超过MOD被取余,后续所有基于余数的乘2、取余操作,得到的每一步结果都和“存完整大数、最终一次性取余”的结果完全等价,从数学上不存在任何误差。
很多人直觉上觉得“必须先把完整的大值算出来再取模”,本质上是混淆了“存全量大值”和“取模等价变形”的区别——我们最终需要的只是一个模1e9+7的余数,根本不需要知道这个数的完整表示是什么。题目中n最大为1e6,循环跑1e6次的计算成本在C++中仅需微秒级,完全不需要额外实现大整数存储来计算全量的2^n值。


内容的提问来源于stack exchange,提问作者Ak01

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.17 04:06:06