本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-11 22:56:18

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

按照套路，先构造矩阵，设 $[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 年的代码