原题链接
题意：维护一段序列，支持区间加和区间斐波那契数列和。
解题思路
显然这题的瓶颈就在于区间加，因为，一堆斐波那契数的下标同时加多少似乎并没有什么公式或者性质……
于是我开始了胡乱思考（
我们知道斐波那契数列的通项公式：
[f_n=frac{1}{sqrt5}left(left(frac{1+sqrt5}{2}
ight)^n-left(frac{1-sqrt5}{2}
ight)^n
ight)
]
然后这里面下标都变成了指数，那么只用维护两三个量，区间加就变成了区间乘……手写一下无理数运算……貌似也可以做。。。
正解显然不是这样，但确实需要把区间加变成区间乘。有什么东西可以通过乘法方便地维护一个递推数列呢？
（好像真有人这么做，还跑得很快？）
使用矩阵
想想你做过的第一道矩阵快速幂题：求 (f_i (1le ile 10^{18}))。
我们有：
[egin{bmatrix}1&1\1&0end{bmatrix}egin{bmatrix}f_i\f_{i-1}end{bmatrix}=egin{bmatrix}f_{i+1}\f_iend{bmatrix}
]
那么我们就可以用线段树在序列上每一个位置维护一个矩阵 (A_i)，假设原数列为 ({a_i})，则
[A_i=egin{bmatrix}f_{a_i}\f_{a_i-1}end{bmatrix}
]
线段树合并区间时可以直接把两个矩阵相加。
区间修改的时候，由于矩阵乘法满足分配律，所以区间加的时候可以直接乘上 (displaystyle{egin{bmatrix}1&1\1&0end{bmatrix}}^x)，(x)为需要加的数。
至于查询时就将包含的区间的矩阵中信息加起来就可以了。
实现细节见代码：
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;
int n,m;
class Matrix22 //实现矩阵类
{
private:
LL a[2][2]; //矩阵用2*2的数组储存
public:
Matrix22(LL a00=0,LL a01=0,LL a10=0,LL a11=0) //构造函数
{ a[0][0]=a00,a[0][1]=a01,a[1][0]=a10,a[1][1]=a11; }
inline LL &operator ()(int i,int j) //更加方便地获取元素
{ return a[i][j]; }
//重载加法和乘法
//因为矩阵大小是固定的所以没有使用for循环
//而且这样常数还比较小（？）
friend inline Matrix22 operator +(const Matrix22 &x,const Matrix22 &y)
{
return Matrix22((x.a[0][0]+y.a[0][0])%MOD,
(x.a[0][1]+y.a[0][1])%MOD,
(x.a[1][0]+y.a[1][0])%MOD,
(x.a[1][1]+y.a[1][1])%MOD);
//对应项相加
}
friend inline Matrix22 operator *(const Matrix22 &x,const Matrix22 &y)
{
return Matrix22((x.a[0][0]*y.a[0][0]+x.a[0][1]*y.a[1][0])%MOD,
(x.a[0][0]*y.a[0][1]+x.a[0][1]*y.a[1][1])%MOD,
(x.a[1][0]*y.a[0][0]+x.a[1][1]*y.a[1][0])%MOD,
(x.a[1][0]*y.a[0][1]+x.a[1][1]*y.a[1][1])%MOD);
//用矩阵乘法法则推一下就可以得到了
}
}base,trans,a[100005];
template<typename T>
T quickPow(T a,LL b) //快速幂
{
T res=a;b--;
while(b)
{
if(b&1) res=res*a;
a=a*a,b>>=1;
}
return res;
}
struct TreeNode //线段树节点，我用了指针写法
{
Matrix22 val,tag;
TreeNode *lc,*rc;
TreeNode(): val(),tag(1,0,0,1) //tag需要初始化为单位矩阵
{ lc=rc=nullptr; }
}*rt;
typedef TreeNode *pNode;
void build(int l,int r,pNode &i=rt) //建树
{
i=new TreeNode;
if(l==r) i->val=a[l];
else
{
int mid=(l+r)>>1;
build(l,mid,i->lc),build(mid+1,r,i->rc);
i->val=i->lc->val+i->rc->val;
}
}
inline void addTag(pNode &i,const Matrix22 &tg) //打tag
{ i->val=tg*i->val,i->tag=tg*i->tag; } //注意这里的tg需要左乘
//矩阵乘法没有交换律，反过来就错了
inline void pushdown(pNode &i) //下传标记
{
addTag(i->lc,i->tag),addTag(i->rc,i->tag);
i->tag=Matrix22(1,0,0,1); //自己的标记重新赋为单位矩阵
}
void modify(int lq,int rq,const Matrix22 &x,int l=1,int r=n,pNode i=rt)
// 区间修改，和板子一模一样
{
if(l>=lq && r<=rq) addTag(i,x);
else
{
int mid=(l+r)>>1;
pushdown(i);
if(mid>=lq) modify(lq,rq,x,l,mid,i->lc);
if(mid<rq) modify(lq,rq,x,mid+1,r,i->rc);
i->val=i->lc->val+i->rc->val;
}
}
LL query(int lq,int rq,int l=1,int r=n,pNode &i=rt)
// 区间查询
{
if(l>=lq && r<=rq) return i->val(0,0); //这里矩阵的(0,0)位置是答案
LL mid=(l+r)>>1,ans=0;
pushdown(i);
if(mid>=lq) ans+=query(lq,rq,l,mid,i->lc);
if(mid<rq) ans+=query(lq,rq,mid+1,r,i->rc);
return ans%MOD;
}
int main()
{
scanf("%d%d",&n,&m);
base(1,0)=trans(0,0)=trans(0,1)=trans(1,0)=1;
// 你看，很方便吧（
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[i]=quickPow(trans,x)*base; //数组a初始化
}
build(1,n);
while(m--) // 应该不用注释了
{
int opt,l,r,x;
scanf("%d%d%d",&opt,&l,&r);
if(opt==1)
scanf("%d",&x),modify(l,r,quickPow(trans,x));
else
printf("%lld
",query(l,r));
}
return 0;
}
这题有50多个测试点，每个测试点5s时限，因此评测异常艰辛（
调完样例后居然一遍过了，而且总时间34s感觉还行