CF575A 大概思路

· · 个人记录

思路好想，被细节创飞了。

按照套路，先构造矩阵，设 [f_i,f_{i+1}] \cdot delta_i = [f_{i+1},f_{i+2}]。

则答案就能用 [0,1] 和 delta 的乘积表示出来了。

然后发现这个 delta 有循环节，每个循环节长度为 n。
于是划分成 \lceil{\frac{k}{n}}\rceil 段，把不考虑特殊点情况下的循环节的答案算出来。
对于不存在循环节的段，矩阵快速幂维护。
对于存在循环节的段，这样的段可以分别单独维护。
考虑对 s 的修改会对 delta 造成的影响，可以发现只会影响两个 delta。
提前把对所有 delta 的影响算出来，然后依次枚举每个段落进行修改，查询答案。

可以用线段树维护一个段的 delta 乘积，并支持修改。
当结束一个段落时，线段树查询 delta 乘积，再将线段树改回原样准备下一个段落。

细节很多，列举几个：

  1. 两个相邻的 si 被修改，会导致同一个 delta 被修改，如果不注意，这两个修改操作结果会互相覆盖。
  2. 最后一段，如果用 k \mod n 计算长度，k 是 n 的倍数就会寄掉。

调了 114514 年的代码