Description

洛谷传送门

Solution

转移方程就是斐波那契数列求和，题目里也都给了。

矩阵也比较基础吧，不写了。

但是这道题需要用到线段树维护矩阵乘法。

听着挺吓人的，其实也没有多难。

我们首先建一棵矩阵类型的线段树。

然后 \(build\) 为初始输入的斐波那契数（即 \(f^{A - 1}\)，因为我们的 \(f\) 矩阵中已经有前两项了，所以次方要 -1）。

区间修改（加上 \(x\)）其实就是乘上 \(x\) 次方。\(lazy\) 标记中存初始矩阵 \(x\) 次方之后的结果。

\(pushdown\) 时，令原来的数直接乘上 \(lazy\) 标记即可。

查询操作，我们线段树中维护的就是区间和，直接查询即可。

Code

代码个人感觉还是比较简明易懂的，不写注释了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long

using namespace std;

inline ll read(){
	ll x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
}

const ll mod = 1e9 + 7;

struct matrix{
	ll num[5][5];
	matrix(){
		memset(num, 0, sizeof(num));
	}
	void init(){
		for(int i = 1; i <= 2; i++)
			num[i][i] = 1;
	}
	bool empty(){
		if(num[1][1] != 1 || num[2][2] != 1 || num[1][2] || num[2][1]) return 0;
		return 1;
	}
	void clear(){
		memset(num, 0, sizeof(num));
	}
	matrix operator * (const matrix &b) const{
		matrix r;
		for(int i = 1; i <= 2; i++)
			for(int j = 1; j <= 2; j++)
				for(int k = 1; k <= 2; k++)
					r.num[i][j] = (r.num[i][j] + num[i][k] * b.num[k][j]) % mod;
		return r;
	}
	matrix operator + (const matrix &b) const{
		matrix r;
		for(int i = 1; i <= 2; i++)
			for(int j = 1; j <= 2; j++)
				r.num[i][j] = (num[i][j] + b.num[i][j]) % mod;
		return r;
	}
	matrix operator ^ (ll p) const{
		matrix r, a;
		memcpy(a.num, num, sizeof(num));
		r.init();
		for(; p; p >>= 1, a = a * a)
			if(p & 1) r = r * a;
		return r;
	}
}f, A;

#define ls rt << 1
#define rs rt << 1 | 1

const ll N = 1e5 + 10;
ll n, m;
ll a[N];
matrix sum[N << 2], lazy[N << 2];

inline void pushup(ll rt){
	sum[rt] = sum[ls] + sum[rs];
}

inline void pushdown(ll l, ll r, ll rt){
	if(lazy[rt].empty()) return;
	ll mid = (l + r) >> 1;
	sum[ls] = sum[ls] * lazy[rt];
	sum[rs] = sum[rs] * lazy[rt];
	lazy[ls] = lazy[ls] * lazy[rt];
	lazy[rs] = lazy[rs] * lazy[rt];
	lazy[rt].clear();
	lazy[rt].init();
}

inline void build(ll l, ll r, ll rt){
	lazy[rt].init();
	if(l == r){
		sum[rt] = f * (A ^ (a[l] - 1));
		return;
	}
	ll mid = (l + r) >> 1;
	build(l, mid, ls);
	build(mid + 1, r, rs);
	pushup(rt);
}

inline void update(matrix x, ll L, ll R, ll l, ll r, ll rt){
	if(L <= l && r <= R){
		sum[rt] = sum[rt] * x;
		lazy[rt] = lazy[rt] * x;
		return;
	}
	pushdown(l, r, rt);
	ll mid = (l + r) >> 1;
	if(L <= mid) update(x, L, R, l, mid, ls);
	if(R > mid) update(x, L, R, mid + 1, r, rs);
	pushup(rt);
}

matrix query(ll L, ll R, ll l, ll r, ll rt){
	if(L <= l && r <= R)
		return sum[rt];
	pushdown(l, r, rt);
	ll mid = (l + r) >> 1;
	matrix res;
	if(L <= mid) res = res + query(L, R, l, mid, ls);
	if(R > mid) res = res + query(L, R, mid + 1, r, rs);
	return res;
}

signed main(){
	f.num[1][1] = f.num[1][2] = 1;
	A.num[1][1] = A.num[1][2] = A.num[2][1] = 1;
	ll n = read(), m = read();
	for(int i = 1; i <= n; i++)
		a[i] = read();
	build(1, n, 1);
	while(m--){
		ll op = read(), l = read(), r = read(), x;
		if(op == 1){
			x = read();
			update(A ^ x, l, r, 1, n, 1);
		}else
			printf("%lld\n", query(l, r, 1, n, 1).num[1][2] % mod);
	}
	return 0;
}

End