本文主要是介绍CF575A Fibonotci 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
CF575A Fibonotci
CF575A Fibonotci
这个题目兴许可以当做动态 D p \tt Dp Dp 入门？
考虑如果直接给定了 s s s 没有修改的话，我们直接对于这些 s s s 矩阵乘起来直接做即可。
考虑题目一个比较简单的形式，就是如果每一段只有一个位置被修改，那么我们直接维护前缀积，后缀积即可。
那么我们推广一下这个本质上就是区间查询单点修改的题目，因为矩阵的逆矩阵不一定存在，我们只能使用线段树进行维护。
我们对于每一段进行单独考虑，修改里面的所有值，之后再改回来即可。
我也不知道为什么我会在这题上耗一个上午。
具体实现方面我们考虑线段树区间变成 0 ∼ n − 1 0 \sim n - 1 0∼n−1 对于位置 i i i 其维护的矩阵是：
[ 0 s i 1 s i + 1 ] \left[ \begin{matrix} 0 & s_i\\ 1 & s_{i + 1} \end{matrix} \right] [01sisi+1]
我们每次修改需要改两个值，为了方便我们将其拆开，这样可以不需要在进行修改的时候进行分类讨论当前位置可能属于两个区间的情况。
#include <bits/stdc++.h>
using namespace std;//#define Fread
//#define Getmod#ifdef Fread
char buf[1 << 21], *iS, *iT;
#define gc() (iS == iT ? (iT = (iS = buf) + fread (buf, 1, 1 << 21, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
#define getchar gc
#endif // Freadtemplate <typename T>
void r1(T &x) {x = 0;char c(getchar());int 这篇关于CF575A Fibonotci 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
