题目来源：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3772

 

分析：

公式来源：http://blog.csdn.net/u013491262/article/details/23089957#comments

 

代码如下：

const int Mod=1000000007;struct Mat{    LL a[2][2];    Mat(){        memset(a,0,sizeof(a));    }    Mat( LL a01)    {        a[0][0]=1;        a[0][1]=a01;        a[1][0]=1;        a[1][1]=0;    }    Mat operator *( Mat m){        Mat ans;        for(int i=0; i<2; i++){            for(int j=0; j<2 ;j++){                for(int k=0 ;k<2; k++){                    ans.a[i][j]=( ans.a[i][j] +  a[i][k]*m.a[k][j] ) % Mod;                }            }        }        return ans;    }};const int Max_N = 100008;Mat sum[Max_N <<2]; // 存的是区间点的矩阵连乘积LL x[Max_N];int N;void push_up(int root){    sum[root]=  sum[root<<1|1] * sum[root<<1];}void make_tree(int L, int R, int root){    if(L == R){        sum[root]=Mat(x[L]);        return;    }    int mid= (L + R)>>1;    make_tree(L, mid , root<<1);    make_tree(mid+1, R, root<<1|1);    push_up(root);}Mat query(int l, int r, int L, int R, int root){    if(l<=L && R <= r)        return sum[root];    int mid=(L + R)>>1;    if(mid >= r)        return query(l,r,L, mid, root<<1);    else if(mid < l)        return query(l,r,mid+1, R, root<<1|1);    else        return query(l,r,mid+1, R, root<<1|1) * query(l , r, L, mid, root<<1);}LL Ans(int L, int R){    if(L > R)        swap(L,R);    if(R==L || R==L+1)        return x[R] % Mod;    Mat m=query(L+2, R , 1,N,1);    return (m.a[0][0] * x[L+1] + m.a[0][1]* x[L]) % Mod;}int main(){    int t,m;    //cin>>t;    scanf("%d",&t);    while(t--){        //cin>>N>>m;        scanf("%d%d",&N,&m);        for(int i=1 ; i<=N ; i++)            scanf("%lld",&x[i]);        make_tree(1,N,1);        while(m--){            int l,r;            //cin>>l>>r;            scanf("%d%d",&l,&r);            //cout<
     
      <