题解 P3404 【斐波那契】
一UNowen一
·
·
题解
一个写完题才发现模数不是1e9+7的ZZ。
给出一种比较简单粗暴的O(Nlogn)做法
容易发现对于一个区间[l,r]，假如对a_{i}加上G(i-l+1)，且G(i)=G(i-1)+G(i-2)(i>2)，那么我们只要确定G(1)和G(2)就可以确定后面所有的影响。
考虑矩乘，可以做到O(n)预处理出n个2*2的矩阵，使得对于第i个矩阵a_{i},G(i)=G(1)*a_{i,0,0}+G(2)*a_{i,0,1},G(i+1)=G(1)*a_{i,0,1}+G(2)*a_{i,1,1}然后用前缀和可以求出n个1*2的矩阵S使得\sum_{i=1}^{k}G(i)=S_{i,0}*G(1)+S_{i,1}*G(2)不了解这方面的可以查矩阵乘法求斐波那契数列第n项。
然后打个标记维护一下G(1)和G(2)就好了。