Codeforces Round #373 C. Sasha and Array（斐波那契数列矩阵形式+矩阵快速幂+线段树）

传送门

题意，给定一个序列，定义f(a)表示斐波那契数列的第a项，
序列涉及两种操作，一是区间每个数加x
二是对于询问[l,r]，输出 Σf(a[i]) (l<=i<=r)，对1e9+7取模。

看到斐波那契数列容易联想到其矩阵形式：
[ f ( 3 ) ( f 2 ) ] = [ f ( 2 ) f ( 1 ) ] ∗ [ 1 1 1 0 ] begin{bmatrix}f(3)&(f2)end{bmatrix} =begin{bmatrix}f(2)&f(1)end{bmatrix} *begin{bmatrix}1&1\1&0end{bmatrix} [f(3)​(f2)​]=[f(2)​f(1)​]∗[11​10​]

我们令F(1)= [ f ( 1 ) f ( 0 ) ] begin{bmatrix}f(1)&f(0)end{bmatrix} [f(1)​f(0)​] = [ 1 0 ] =begin{bmatrix}1&0end{bmatrix} =[1​0​]

记矩阵E= [ 1 1 1 0 ] begin{bmatrix}1&1\1&0end{bmatrix} [11​10​]

则 F(x) = F(1)* E^(x-1) = [ f ( x ) f ( x − 1 ) ] begin{bmatrix}f(x)&f(x-1)end{bmatrix} [f(x)​f(x−1)​]

那么询问就等价于 : ΣF(a[i]) = ΣF(1) * E^(a[i]-1)，计算结果的(0,0)位置就是答案了。

由于矩阵乘法是具有分配律和结合律的，所以我们可以把数列看成一个矩阵,a[i]对应成E^(a[i]-1)，每次修改相当于区间每个数都乘以E^(x) ,
所以用线段树维护区间和，区间修改。
每次查询区间矩阵之和。

细节：

1、懒标记tag[rt]的写法，如果记写成区间加某个数的话，每次pushdown都要做一次矩阵快速幂，常数巨大，毫无疑问tle。所以要写成一个矩阵，也就是E^x，每次tag更新也是和新的修改信息乘起来。

2、注意开longlong!

#include
using namespace std;
//#pragma GCC optimize(2)
#define ull unsigned long long
#define ll long long
#define pii pair
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = (ll)4e16+5;
const int INF = 1e9 + 7;
const double pi = acos(-1.0);
ll inv(ll b){if(b==1)return 1;return(mod-mod/b)*inv(mod%b)%mod;}
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct ma 
{
    ll a[2][2];
    void init()
    {
        a[0][0]=1;a[0][1]=1;
        a[1][0]=1;a[1][1]=0;
    }
    void clear()
    {
        a[0][0]=1;a[0][1]=0;
        a[1][0]=0;a[1][1]=1;
    }
    bool isE()//是否为单位矩阵
    {
        return (a[0][0]==1 && a[0][1]==0 && a[1][0]==0 && a[1][1]==1);
    }
    ma operator * (const ma &f)const 
    {
        ma ret;
        memset(ret.a,0,sizeof ret.a);
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    ret.a[i][j]=(ret.a[i][j] + a[i][k]*f.a[k][j]%mod)%mod;
                }
            }
        }
        return ret;
    }
}e;//递推矩阵
ma operator ^ (ma a1,ll b)//a^b ksm
{
    ma ans;
    ans.clear();
    while(b)
    {
        if(b&1) ans=ans*a1;
        b>>=1;
        a1=a1*a1;
    }
    return ans;
}
ma operator + (ma a1,ma b)
{
    ma ret;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++) ret.a[i][j]=(a1.a[i][j]+b.a[i][j])%mod;
    }
    return ret;
}
int n,m;
//线段树维护矩阵序列的区间和  每次区间更新 区间每个矩阵乘一个矩阵I^x 
//FX={f(x),f(x-1)}  F1={1,0} 最终用F1乘区间和 得到的矩阵第一个元素就是答案
struct node 
{
    #define lc rt<<1
    #define rc rt<<1|1
    int l,r;
    ma fv;
}tree[maxn<<2];
ma tag[maxn<<2];//初始为单位矩阵 不用乘
inline void pushup(int rt)
{
    tree[rt].fv=tree[lc].fv+tree[rc].fv;
}
inline void build(int rt,int l,int r)
{
    tree[rt].l=l,tree[rt].r=r;
    tag[rt].clear();
    if(l==r) 
    {
        ll x;
        scanf("%lld",&x);
        tree[rt].fv=e^(x-1);
        return ;
    }
    int mid=l+r>>1;
    build(lc,l,mid);build(rc,mid+1,r);
    pushup(rt);
}
inline void change(int rt,ma &mt) 
{
    tree[rt].fv = tree[rt].fv*mt;
    tag[rt]=tag[rt]*mt;
}
inline void pushdown(int rt)
{
    if(!tag[rt].isE()) //是单位矩阵就不用乘
    {
        change(lc,tag[rt]);
        change(rc,tag[rt]);
        tag[rt].clear();
    }
}
inline void upd(int rt,int vl,int vr,ma &mt)
{
    int l=tree[rt].l,r=tree[rt].r;
    if(rvr) return ;
    if(vl<=l && r<=vr) 
    {
        change(rt,mt);
        return ;
    }
    pushdown(rt);
    upd(lc,vl,vr,mt);upd(rc,vl,vr,mt);
    pushup(rt);
}
inline ma qry(int rt,int vl,int vr)
{
    int l=tree[rt].l,r=tree[rt].r;
    if(vl<=l && r<=vr) 
    {
        return tree[rt].fv;
    }
    int mid=l+r>>1;
    pushdown(rt);
    if(vr<=mid) return qry(lc,vl,vr);
    else if(vl>mid) return qry(rc,vl,vr);
    return qry(lc,vl,vr) + qry(rc,vl,vr);
}
int main()
{
    e.init();
    scanf("%d %d",&n,&m);
    build(1,1,n);
    int f,l,r;
    ll x;
    while(m--)
    {
        scanf("%d %d %d",&f,&l,&r);
        if(f==1) 
        {
            scanf("%lld",&x);
            ma t=e^x;
            upd(1,l,r,t);
        }
        else 
        {
            ma temp=qry(1,l,r);
            ll ans=( 1ll*temp.a[0][0] + 0*temp.a[0][1] ) %mod;
            printf("%lldn",ans);
        }
    }
    return 0;
}