CF446C

题目链接

description

写个数据结构，支持区间加斐波那契数列和区间求和。

模 1e9+9。

solution

设 \(A=\begin{bmatrix}1&1 \\ 1 & 0 \end{bmatrix}\)。

则 \(\begin{bmatrix} F_{n+1}& F_{n} \end{bmatrix}=\begin{bmatrix}1&0 \end{bmatrix} \times A^n\)。

于是问题变成了区间加公比一定的等比数列。

对于区间 \([l,r]\)，如果要加上 \(A^p+A^{p+1}\dots +A^{p+r-l}\)，可以先提一个 \(A^{p-1}\) 出来，然后变成了 \(A^{p-1}\times(A^1+A^2+\dots+A^{r-l+1})\)。（矩阵乘法满足对矩阵加法的分配率）。

于是我们在线段树上维护每个节点加了的 \(A^{p-1}\) 的和 \(sum\)，询问求值的时候返回 \(sum\times (A^1+A^2+\dots+A^{r-l+1})\) 即可。

下传标记时，给左二子传 \(A^{tag}\)，右儿子传 \(A^{tag+mid-l+1}\)（显然这样的标记是满足可加性的）。

预处理矩阵幂次，时间复杂度 \(O((n+q)\log n)\)

hint

关键是把斐波那契数列转化成矩阵，找到合适的方法（满足标记可加）去维护区间。

2*2 的矩阵常数也不小，注意到 \(5\) 是模 1e9+9 下的二次剩余，可以先算出 \(\sqrt{5}\) ，然后用类似的办法维护（把矩阵换成斐波那契数列通项公式）。我的代码实现用的是矩阵。

code

参考代码链接：Submission #222048918 - Codeforces