题目描述

给你$n$个数,支持两个操作

  1. $\forall i \in [l,r] \cap Z,a_i \leftarrow a_i + x$
  2. 查询$\sum_{i=l}^{r}f(a_i)$

其中$f(0)=0,f(1)=1$,且$\forall i \ge 2 \wedge i \in Z,f(i)=f(i-1)+f(i-2)$

题解

先列出转移矩阵

$$
\begin{pmatrix}
f(i+1) & f(i)
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
=
\begin{pmatrix}
f(i+2) & f(i+1)
\end{pmatrix}
$$

所以

$$
\begin{pmatrix}
f(1) & f(0)
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
=
\begin{pmatrix}
f(n) & f(n-1)
\end{pmatrix}
=
\begin{pmatrix}
1 & 0
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
$$

$$
\begin{cases}
B = \begin{pmatrix} 1 & 0 \end{pmatrix} \\
M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\end{cases}
$$

$$
\begin{align}
&\sum_{i=l}^{r}f(a_i+x) \\
=&\sum_{i=l}^{r}B \times M^{a_i-1+x} \\
=&B(M^x\sum_{i=l}^{r}M^{a_i-1})
\end{align}
$$

用线段树实现区间乘一个矩阵、维护区间矩阵和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10, p = 1e9 + 7;
typedef long long ll;

struct Mat {
ll a[2][2];
Mat() { memset(a, 0, sizeof a); }
ll* operator [] (int i) { return a[i]; }
bool notI() {
return !(a[0][0] == 1 && a[0][1] == 0
&& a[1][0] == 0 && a[1][1] == 1);
}
Mat operator * (Mat b) {
Mat c;
for(int i = 0 ; i < 2 ; ++ i)
for(int j = 0 ; j < 2 ; ++ j)
for(int k = 0 ; k < 2 ; ++ k)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % p;
return c;
}
Mat operator + (Mat b) {
Mat 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;
}
void output() {
puts("\n---");
for(int i = 0 ; i < 2 ; ++ i, puts(""))
for(int j = 0 ; j < 2 ; ++ j)
printf("%d ", a[i][j]);
puts("---\n");
}
} mat[N * 4], M, B, tag[N * 4], I;

#define lc (id << 1)
#define rc (id << 1 | 1)

Mat pw(Mat a, ll b) {
Mat c = I;
for( ; b ; b >>= 1, a = a * a) if(b & 1) c = c * a;
return c;
}

void update(int id) {
mat[id] = mat[lc] + mat[rc];
}

void push(int id) {
if(id && tag[id].notI()) {
tag[lc] = tag[lc] * tag[id], tag[rc] = tag[rc] * tag[id];
mat[lc] = mat[lc] * tag[id], mat[rc] = mat[rc] * tag[id];
tag[id] = I;
}
}

void build(int id, int l, int r) {
int mid = (l + r) >> 1;
tag[id] = I;
if(l == r) {
int x; scanf("%d", &x);
mat[id] = B * pw(M, x - 1);
} else {
build(lc, l, mid), build(rc, mid + 1, r);
update(id);
}
}

void modify(int id, int l, int r, int ql, int qr, Mat x) {
push(id);
int mid = (l + r) >> 1;
if(ql <= l && r <= qr) return tag[id] = tag[id] * x, mat[id] = mat[id] * x, void();
else if(qr <= mid) modify(lc, l, mid, ql, qr, x);
else if(ql >= mid + 1) modify(rc, mid + 1, r, ql, qr, x);
else modify(lc, l, mid, ql, mid, x), modify(rc, mid + 1, r, mid + 1, qr, x); update(id);
}

ll query(int id, int l, int r, int ql, int qr) {
push(id);
int mid = (l + r) >> 1;
if(ql <= l && r <= qr) return mat[id][0][1];
else if(qr <= mid) return query(lc, l, mid, ql, qr);
else if(ql >= mid + 1) return query(rc, mid + 1, r, ql, qr);
else return (query(lc, l, mid, ql, mid) + query(rc, mid + 1, r, mid + 1, qr)) % p;
}

int n, m;

int main() {
B[0][0] = 1, B[0][1] = 1;
B[1][0] = 0, B[1][1] = 0;

I[0][0] = 1, I[0][1] = 0;
I[1][0] = 0, I[1][1] = 1;

M[0][0] = 1, M[0][1] = 1;
M[1][0] = 1, M[1][1] = 0;
scanf("%d%d", &n, &m);
build(1, 1, n);
for(int i = 1, op, l, r, x ; i <= m ; ++ i) {
scanf("%d%d%d", &op, &l, &r);
if(op == 1) {
scanf("%d", &x);
modify(1, 1, n, l, r, pw(M, x));
} else {
printf("%I64d\n", query(1, 1, n, l, r));
}
}
}