16.CF718C Sasha and Array 线段树+矩阵快速幂

16.CF718C Sasha and Array 线段树+矩阵快速幂

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

要求支持区间和操作，查询元素作为下标时的斐波那契和

转换为矩阵快速幂形式，用线段树解决。

洛谷传送门：CF718C Sasha and Array - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：C. Sasha and Array (codeforces.com)

题目分析

转换为矩阵快速幂形式，区间加 X X X的操作即可表示为区间的所有矩阵全部乘转移矩阵的 x x x次方

区间查询斐波那契和即为区间矩阵和第二项(视具体情况而定)

关键点：斐波那契矩阵快速幂做法满足可加性(运算结果即答案)和乘法分配律 ( a ∗ c + b ∗ c = ( a + b ) ∗ c ) (a * c + b * c = (a + b) * c) (a∗c+b∗c=(a+b)∗c)

此外，你还需要一个比较好用的矩阵运算类。这里我习惯用ECNU的板子…

关于矩阵快速幂的讲解：这里直接放Fib的讲解，具体可以参考我之前的博客：矩阵快速幂 - HeartFireY

给定整数 n n n，计算斐波那契数列的第 n n n项 F n F_n Fn​。

首先，观察斐波那契数列的特征：递推公式： F n = F n − 1 + F n − 2 F_n = F_{n-1} + F_{n-2} Fn​=Fn−1​+Fn−2​

我们不难发现： F n F_n Fn​与 F n − 1 F_{n- 1} Fn−1​和 F n − 1 F_{n - 1} Fn−1​与 F n − 2 F_{n -2} Fn−2​之间的关系可以用矩阵的乘法关系进行描述： [ F n − 1 F n ]   =   [ F n − 2 F n − 1 ]   ⋅   [ 0 1 1 1 ] \begin{bmatrix} F_{n - 1}&F_{n}\\ \end{bmatrix} \ = \ \begin{bmatrix} F{n - 2}&F_{n - 1} \end{bmatrix} \ \cdot \ \begin{bmatrix} 0&1\\ 1&1\\ \end{bmatrix} [Fn−1​​Fn​​] = [Fn−2​Fn−1​​] ⋅ [01​11​] 不妨设 P = [ 0 1 1 1 ] P = \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix} P=[01​11​]，改写递推公式，可得： [ F n F n + 1 ] = [ F 0 F 1 ] ⋅ P n \begin{bmatrix}F_n & F_{n+1} \cr\end{bmatrix} = \begin{bmatrix}F_0 & F_1 \cr\end{bmatrix} \cdot P^n [Fn​​Fn+1​​]=[F0​​F1​​]⋅Pn 于是我们可以用矩阵乘法在 Θ ( log ⁡ n ) \Theta(\log n) Θ(logn) 的时间内计算斐波那契数列。那么本题我们只需要维护区间乘ji’ke

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N];

namespace ffastIO {
	const int bufl = 1