CF719E. Sasha and Array

题意：

对长度为 n 的数列进行 m 次操作, 操作为:

1. a[l..r] 每一项都加一个常数 C, 其中 0 ≤ C ≤ 10^9
2. 求 F[a[l]]+F[a[l+1]]+...F[a[r]] mod 1e9+7 的余数

---

矩阵快速幂求斐波那契

矩阵满足乘法分配律和结合律！

所以可以每个节点维护矩阵/矩阵和，区间加相当于区间乘矩阵

注意：不要把快速幂写在里面，复杂度平添一个log。把\(B^C\)算出来之后传进去就好了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

#define lc x<<1

#define rc x<<1|1

#define mid ((l+r)>>1)

#define lson lc, l, mid

#define rson rc, mid+1, r

const int N = 1e5+5, P = 1e9+7;

int n, m;

struct Matrix {

	ll a[2][2];

	ll* operator [](int x) {return a[x];}

	Matrix(int p=0) {

		if(!p) a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;

		else a[0][0] = a[1][1] = 1, a[0][1] = a[1][0] = 0;

	}

} B;

Matrix operator + (Matrix a, Matrix b) {

	Matrix c;

	for(int i=0; i<2; i++)

		for(int j=0; j<2; j++)

			c[i][j] = (a[i][j] + b[i][j]) %P;

	return c;

}

Matrix operator * (Matrix a, Matrix b) {

	Matrix c;

	for(int i=0; i<2; i++)

		for(int j=0; j<2; j++) {

			ll &x = c[i][j];

			for(int k=0; k<2; k++)

				x = (x + a[i][k] * b[k][j] %P) %P;

		}

	return c;

}

Matrix operator ^ (Matrix a, int b) {

	Matrix ans(1);

	ans[0][0] = ans[1][1] = 1;

	for(; b; b>>=1, a=a*a)

		if(b & 1) ans = ans*a;

	return ans;

}

struct meow {

	Matrix f;

	Matrix v;

	int c;

	meow() {f[0][0] = 1; v[0][0] = v[1][1] = 1;}

} t[N<<2];

void paint(int x, int l, int r, int d, Matrix &v) {

	t[x].c += d;

	t[x].v = v * t[x].v;

	t[x].f = v * t[x].f;

}

void push_down(int x, int l, int r) {

	if(t[x].c) {

		paint(lson, t[x].c, t[x].v);

		paint(rson, t[x].c, t[x].v);

		t[x].c = 0;

		t[x].v = Matrix(1);

	}

}

void merge(int x) {

	t[x].f = t[lc].f + t[rc].f;

}

void build(int x, int l, int r) {

	if(l == r) {

		cin >> t[x].c;

		if(t[x].c > 1) t[x].f = (B ^ (t[x].c - 1)) * t[x].f;

	} else {

		build(lson);

		build(rson);

		merge(x);

	}

}

void Add(int x, int l, int r, int ql, int qr, int d, Matrix &v) {

	if(ql <= l && r <= qr) paint(x, l, r, d, v);

	else {

		push_down(x, l, r);

		if(ql <= mid) Add(lson, ql, qr, d, v);

		if(mid < qr)  Add(rson, ql, qr, d,v );

		merge(x);

	}

}

ll Que(int x, int l, int r, int ql, int qr) {

	if(ql <= l && r <= qr) return t[x].f[0][0];

	else {

		push_down(x, l, r);

		ll ans = 0;

		if(ql <= mid) ans = (ans + Que(lson, ql, qr)) %P;

		if(mid < qr)  ans = (ans + Que(rson, ql, qr)) %P;

		return ans;

	}

}

int main() {

	//freopen("in", "r", stdin);

	ios::sync_with_stdio(false); cin.tie(); cout.tie();

	B[0][0] = B[0][1] = B[1][0] = 1;

	cin >> n >> m;

	build(1, 1, n);

	for(int i=1; i<=m; i++) {

		int tp, l, r, x;

		cin >> tp >> l >> r;

		if(tp == 1) {

			cin >> x;

			Matrix t = B^x;

			Add(1, 1, n, l, r, x, t);

		} else cout << Que(1, 1, n, l, r) << '\n';

	}