CF718C Sasha and Array

CF718C Sasha and Array

题目大意

• 在本题中，我们用 \(f_i\) 来表示第 \(i\) 个斐波那契数（\(f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)\)）。
• 给定一个 \(n\) 个数的序列 \(a\)。有 \(m\) 次操作，操作有两种：
  1. 将 \(a_l\sim a_r\) 加上 \(x\)。
  2. 求 \(\displaystyle\left(\sum_{i=l}^r f_{a_i}\right)\bmod (10^9+7)\)。
• \(1\le n,m\le 10^5\)，\(1\le a_i\le 10^9\)。

分析

题目倒是不难，我们看到想要快速的求出大项的Fibonacci Number时，就知道想到用矩阵乘法。

两个操作

1. 第一个操作，我们只要将区间乘上转移矩阵x次方即可。
2. 第二个操作，就直接维护和即可。

这里说一下为什么可以直接维护和即可，这里是依据矩阵的结合律来的，\(a\times b+c\times b=(a+c)\times b\)，因此区间每个矩阵乘转移矩阵，等于其和乘转移矩阵。

AC_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10,mod = 1e9 + 7;

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(){
        clear();
		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=%d,j=%d,m=%d\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]+1ll*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]=(1ll*a.m[i][j]+b.m[i][j])%mod;
		}
		return c;
	}

    int* operator[](int x)
    {
        return m[x];
    }
};

struct Node
{
    int l,r;
    Matrix val,mul;
}tr[N<<2];

int n,m;
int a[N];
Matrix dw,fir;

Matrix mpow(Matrix a,int n)
{
    Matrix c;c.init();
    while(n)
    {
        if(n&1) c = c*a;
        a = a*a;
        n>>=1;
    }
    return c;
}

void pushup(int u)
{
    tr[u].val = tr[u<<1].val + tr[u<<1|1].val;
}

void build(int u,int l,int r)
{
    tr[u] = {l,r};
    tr[u].mul.init();
    if(l==r)
    {   
        tr[u].val = fir*mpow(dw,a[l]-1);
        return ;
    }
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

void pushdown(int u)
{
    auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
    if(!root.mul.empty())
    {
        left.val = left.val*root.mul;
        left.mul = left.mul*root.mul;
        right.val = right.val*root.mul;
        right.mul = right.mul*root.mul;
        root.mul.init();
    }
}

void modify(int u,int l,int r,Matrix k)
{
    if(l<=tr[u].l&&tr[u].r<=r) 
    {
        tr[u].val = tr[u].val*k;
        tr[u].mul = tr[u].mul*k;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l<=mid) modify(u<<1,l,r,k);
    if(r>mid) modify(u<<1|1,l,r,k);
    pushup(u);
}

int query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].val[1][1];
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    int res = 0;
    if(l<=mid) res = (1ll*res + query(u<<1,l,r))%mod;
    if(r>mid) res = (1ll*res + query(u<<1|1,l,r))%mod;
    return res;
}

int main()
{
    ios;
    cin>>n>>m;
    dw[1][1] = 0,dw[1][2] = 1,dw[2][1] = 1,dw[2][2] = 1; 
    fir.clear();
    fir[1][1] = fir[1][2] = 1;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int op,l,r;cin>>op>>l>>r;
        if(op==1) 
        {
            int x;cin>>x;
            Matrix res = mpow(dw,x);
            modify(1,l,r,res);
        }
        else cout<<query(1,l,r)<<'\n';
    }
    return 0;
}