关于此题lz用int一些写法的问题
查看原帖
关于此题lz用int一些写法的问题
711690
cowardTester楼主2024/3/21 20:10
  • 即用 lzidlz_{id} 表示线段树上点 idid 所有后代的和矩阵要 ×baselzid\times base^{lz_{id}}(basebase 表示矩阵快速幂中的底数)。

  • 于是更新儿子节点和矩阵时需要计算 baselzbase^{lz}。而这是模意义下的,在更新 lzlz 时我们习惯性地对 PP 取模,这是错误的,basexbase^x 与 basexmod  Pbase^{x \mod P} 在模 PP 意义下并不同余。

  • 改进措施:

  1. lzlz 对 P−1P-1 取模(欧拉降幂);
  2. lzlz 直接用矩阵表示,即上面 baselzbase^{lz},这样在乘的时候就可以取模,而每次加的数不超过 10910^9。
  • 当然,第一种改进措施在 pushdown 时因快速幂要多花费一个 log⁡\log,实现中采用第二种。
2024/3/21 20:10
加载中...