栗子栗子

CodeForces 719E

CodeForces 719E Sasha and Array

题目

题目大意

给定一个数列$a_i$,$n$个数,$m$个操作或查询,$n,m\leq100000,a_i\leq10^9$

每次可进行操作(对$l$~$r$区间内的数加上$x$)

或者查询(输出$(\sum_{i=l}^rf(a_i))mod10^9+7$,其中$f(a_i)$定义为$Fibonacci$数列的第$a_i$项 )

思路

考虑到$Fibonacci$数列的求项问题,第一反应显然是矩阵快速幂咯~

通过观察我们注意到,对于矩阵$A,B,C$,$A(B+C)=AB+AC$

即矩阵乘法满足分配律

这样有什么用呢,我们看到剩下的要求:区间修改,区间查询

一个经典的动态RMQ问题,可以使用线段树($Segment Tree$)解决

这时候我们就发现此处分配律的重要性了,正是因为可以对矩阵求和使其方便的计算$Fibonacci$数列的若干项和

我们这里的线段树才得以使用。

综上,思路如下,

建立一颗线段树,每个节点下建立一个量保存求$Fibonacci$的快速幂矩阵,然后维护线段树即可。

代码

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const LL mod=1e9+7;
const int maxn=100005;

struct mat
{
int n;
LL num[3][3];

bool law1()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j && num[i][j]!=0)return false;
if(i==j && num[i][j]!=1)return false;
}
return true;
}

void init0(int t)
{
n=t;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
num[i][j]=0;
}

void init1(int t)
{
n=t;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
if(i!=j)num[i][j]=0;else num[i][j]=1;
}

mat operator + (const struct mat p)const
{
struct mat q;
q.init0(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
q.num[i][j]=(num[i][j]+p.num[i][j])%mod;
return q;
}

mat operator * (const struct mat p)const
{
struct mat ans;
ans.init0(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
ans.num[i][j]=(ans.num[i][j]+num[i][k]*p.num[k][j])%mod;
return ans;
}

mat operator ^ (int t)const
{
struct mat ans,now;
ans.init1(n);
now.n=n;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
now.num[i][j]=num[i][j];
while(t>0)
{
if(t&1)ans=ans*now;
now=now*now;
t>>=1;
}
return ans;
}

}c[maxn];

struct tree
{
int ls,rs,ll,rr;
struct mat mi,add;
}a[3*maxn];

int i,j,k,l,m,n,t,T;

void update(int x)
{
if(a[x].ls+a[x].rs==0)return;
a[x].mi=a[a[x].ls].mi+a[a[x].rs].mi;
}

void downdate(int x)
{
if(a[x].ls+a[x].rs==0)return;
if(a[x].add.law1())return;
a[a[x].ls].add=a[a[x].ls].add*a[x].add;
a[a[x].ls].mi=a[a[x].ls].mi*a[x].add;
a[a[x].rs].add=a[a[x].rs].add*a[x].add;
a[a[x].rs].mi=a[a[x].rs].mi*a[x].add;
a[x].add.init1(2);
}

void mt(int l,int r)
{
a[k].add.init1(2);
if(l==r)
{
a[k].ll=a[k].rr=l;
a[k].mi=c[l];
a[k].ls=a[k].rs=0;
return;
}
int t=k;
int mid=(l+r)>>1;
a[t].ll=l;a[t].rr=r;
k++;a[t].ls=k;mt(l,mid);
k++;a[t].rs=k;mt(mid+1,r);
update(t);
}

void add(int l,int r,mat nu,int x)
{
if(a[x].ll==l && a[x].rr==r)
{
a[x].add=a[x].add*nu;
a[x].mi=a[x].mi*nu;
return;
}
downdate(x);
int mid=(a[x].ll+a[x].rr)>>1;
if(mid<l)add(l,r,nu,a[x].rs);
else if(mid>=r)add(l,r,nu,a[x].ls);
else
{
add(l,mid,nu,a[x].ls);
add(mid+1,r,nu,a[x].rs);
}
update(x);
}

mat find(int l,int r,int x)
{
if(a[x].ll==l && a[x].rr==r)return a[x].mi;
downdate(x);
update(x);
int mid=(a[x].ll+a[x].rr)>>1;
if(mid<l)return find(l,r,a[x].rs);
if(mid>=r)return find(l,r,a[x].ls);
return find(l,mid,a[x].ls)+find(mid+1,r,a[x].rs);
}

inline void read(int &x) {
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
x=0;
while(ch<='9'&&ch>='0'){
x=x*10+ch-'0';
ch=getchar();
}
}

int main()
{
struct mat unit;
unit.init0(2);
unit.num[1][1]=unit.num[1][2]=unit.num[2][1]=1;
unit.num[2][2]=0;
read(n);read(m);
for(i=1;i<=n;i++)
{
read(k);
c[i]=unit^(k-1);
}
k=1;mt(1,n);
for(i=1;i<=m;i++)
{
read(j);
if(j==1)
{
read(j);read(k);read(l);
add(j,k,unit^l,1);
}else
{
read(j);read(k);
struct mat ans=find(j,k,1);
printf("%lld\n",ans.num[1][1]);
}
}
return 0;
}