原题：ZOJ 3772 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3772
这题算是长见识了，还从没坐过矩阵+线段树的题目呢，不要以为矩阵就一定配合快速幂来解递推式的哦。
由F(x)=F(x-1)+F(x-2)*A[x]，转化为矩阵乘法：
===》
所以维护一颗线段树，线段树的每个结点保存一个矩阵，叶子节点为： a[0][0] = a[1][0] = 1, a[0][1] = Ax, a[1][1] = 0的形式
否则保存 a[r] * a[r-1] * ... * a[l] 的结果矩阵，且要注意不要乘反了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define Mod 1000000007
#define ll long long
using namespace std;
#define N 100007 struct Matrix
{
ll m[][];
Matrix(int _x)
{
m[][] = ;
m[][] = _x;
m[][] = ;
m[][] = ;
}
Matrix(){}
}tree[*N];
ll A[N]; Matrix Mul(Matrix a,Matrix b)
{
Matrix c;
memset(c.m,,sizeof(c.m));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j])%Mod;
return c;
} void build(int l,int r,int rt)
{
if(l == r)
{
tree[rt] = Matrix(A[l]);
return;
}
int mid = (l+r)/;
build(l,mid,*rt);
build(mid+,r,*rt+);
tree[rt] = Mul(tree[*rt+],tree[*rt]); //注意不要乘反了
} Matrix query(int l,int r,int aa,int bb,int rt)
{
if(aa<=l && bb>=r)
return tree[rt];
int mid = (l+r)/;
if(aa>mid)
return query(mid+,r,aa,bb,*rt+);
else if(bb<=mid)
return query(l,mid,aa,bb,*rt);
else
return Mul(query(mid+,r,aa,bb,*rt+),query(l,mid,aa,bb,*rt)); //不要乘反
} int main()
{
int n,m;
int i,t;
int aa,bb;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
scanf("%lld",&A[i]);
build(,n,);
while(m--)
{
scanf("%d%d",&aa,&bb);
if(bb-aa<=)
printf("%lld\n",A[bb]);
else
{
Matrix ans = query(,n,aa+,bb,);
ll res = ans.m[][]*A[aa+]%Mod + ans.m[][]*A[aa]%Mod;
printf("%lld\n",res%Mod);
}
}
}
return ;
}