题解 CF718C 【Sasha and Array】
YoungNeal
2018-05-30 21:48:36
~~哦我这份代码好像能过QWQ~~
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9113761.html)效果更佳哦~
## Description
给定一个数列，维护两种操作
操作 $1$，将区间 $[l,r]$ 的数字统一加 $x$。
操作 $2$，求 $\sum \limits_{i=l}^r f(val[i])$，其中 $f(i)$ 表示斐波那契数列的第 $i$ 项。‘
答案对 $10^9+7$ 取模。
## Solution
线段树维护矩阵。
因为是斐波那契数列，容易想到用矩阵快速幂来求这个东西。
想这样做的话，要想清楚两个问题：
1. 因为题目中求的是和，那么知道 $[l,mid]$ 和$[mid+1,r]$ 的答案能否快速合并出 $[l,r]$ 的答案呢？
2. 如果知道了 $[l,r]$ 的答案，对于区间加 $x$ 操作，能否快速得知操作后的答案呢？
对于第一个问题，由于矩阵具有分配律，即 $a\times b+a\times c=a\times(b+c)$，所以对于一段区间的矩阵可以相加维护。
对于第二个问题，显然将 $[l,r]$ 的矩阵乘上转移矩阵的 $x$ 次方即可。
综上，两个问题想清楚之后，我们用线段树来维护区间中的矩阵。
## Code
```cpp
// By YoungNeal
#include<cstdio>
#include<cctype>
#define N 100005
#define int long long
const int mod=1e9+7;
int n,m;
int val[N];
struct Matrix{
int m[4][4];
void clear(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++)
m[i][j]=0;
}
}
void init(){
for(int i=0;i<4;i++)
m[i][i]=1;
}
void print(){
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++)
printf("i=%I64d,j=%I64d,m=%I64d\n",i,j,m[i][j]);
}
}
bool empty(){
if(m[1][1]!=1) return 0;
if(m[1][2]!=0) return 0;
if(m[2][1]!=0) return 0;
if(m[2][2]!=1) return 0;
return 1;
}
Matrix operator*(const Matrix &y) const {
Matrix z; z.clear();
for(int i=1;i<=2;i++){
for(int k=1;k<=2;k++){
for(int j=1;j<=2;j++)
z.m[i][j]=(z.m[i][j]+m[i][k]*y.m[k][j])%mod;
}
}
return z;
}
friend Matrix operator+(Matrix a,Matrix b){
Matrix c;c.clear();
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++)
c.m[i][j]=(a.m[i][j]+b.m[i][j])%mod;
}
return c;
}
};
Matrix dw,fir;
Matrix mat[N<<2],lazy[N<<2];
int getint(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
Matrix ksm(Matrix a,int b){
Matrix ret; ret.clear(); ret.init();
while(b){
if(b&1) ret=ret*a;
a=a*a;
b>>=1;
}
return ret;
}
void pushup(int cur){
mat[cur]=mat[cur<<1]+mat[cur<<1|1];
}
void build(int cur,int l,int r){
mat[cur].clear();
lazy[cur].clear();
lazy[cur].init();
if(l==r){
mat[cur]=fir*ksm(dw,val[l]-1);
return;
}
int mid=l+r>>1;
build(cur<<1,l,mid);
build(cur<<1|1,mid+1,r);
pushup(cur);
}
void pushdown(int cur,int l,int r){
if(lazy[cur].empty()) return;
mat[cur<<1]=mat[cur<<1]*lazy[cur];
lazy[cur<<1]=lazy[cur<<1]*lazy[cur];
mat[cur<<1|1]=mat[cur<<1|1]*lazy[cur];
lazy[cur<<1|1]=lazy[cur<<1|1]*lazy[cur];
lazy[cur].clear();
lazy[cur].init();
}
void modify(int cur,int ql,int qr,int l,int r,Matrix x){
if(ql<=l and r<=qr){
mat[cur]=mat[cur]*x;
lazy[cur]=lazy[cur]*x;
return;
}
pushdown(cur,l,r);
int mid=l+r>>1;
if(ql<=mid)
modify(cur<<1,ql,qr,l,mid,x);
if(mid<qr)
modify(cur<<1|1,ql,qr,mid+1,r,x);
pushup(cur);
}
Matrix query(int cur,int ql,int qr,int l,int r){
if(ql<=l and r<=qr)
return mat[cur];
pushdown(cur,l,r);
Matrix ret;ret.clear();
int mid=l+r>>1;
if(ql<=mid)
ret=ret+query(cur<<1,ql,qr,l,mid);
if(mid<qr)
ret=ret+query(cur<<1|1,ql,qr,mid+1,r);
return ret;
}
signed main(){
dw.clear(); fir.clear();
dw.m[1][1]=1;fir.m[1][1]=1;
dw.m[1][2]=1;fir.m[1][2]=1;
dw.m[2][1]=1;fir.m[2][1]=0;
dw.m[2][2]=0;fir.m[2][2]=0;
n=getint(),m=getint();
for(int i=1;i<=n;i++)
val[i]=getint();
build(1,1,n);
while(m--){
if(getint()==1){
int l=getint(),r=getint(),x=getint();
modify(1,l,r,1,n,ksm(dw,x));
}
else{
int l=getint(),r=getint();
printf("%I64d\n",query(1,l,r,1,n).m[1][2]%mod);
}
}
return 0;
}
```