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

// 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;
}

版权声明：本文为YoungNeal原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/YoungNeal/p/9113761.html