给出一些数组a[i]，每次询问为li,ri，定义f[li]=a[li],f[li+1]=a[li+1]，对于其他不超过ri的位置，f[x]=f[x-1]+a[x]*f[x-2] 。

题目有着浓浓的矩阵气息。

f[x]=f[x-1]+a[x]*f[x-2] 

f[x-1]=f[x-1]+0

根据上面两个我们就可以知道

f[x]=========|1,a[x]|         f[x-1]

f[x-1]=======|1 ,  0|         f[x-2]

这样我们就把矩阵构造出来了，相当于每次询问某一段区间的矩阵的乘积。

由于是连续的区间，线段树即可解决问题。

注意矩阵是放在左边，所以大的位置放在左边，线段树操作的时候也需要注意了。

 

 

召唤代码君：

 

 

#include 
     
      #include 
      
       #include 
       
        #define maxn 300300#define mod 1000000007typedef long long ll;using namespace std;class Mat{public:    ll f[2][2];    Mat() { f[0][0]=f[1][1]=f[0][1]=f[1][0]=0; }    Mat(int f1,int f2,int f3,int f4){        f[0][0]=f1,f[0][1]=f2,f[1][0]=f3,f[1][1]=f4;    }    Mat operator * (Mat m1) const{        Mat m0;        for (int i=0; i<2; i++)            for (int j=0; j<2; j++)                for (int k=0; k<2; k++)                    m0.f[i][j]=(m0.f[i][j]+f[i][k]*m1.f[k][j])%mod;        return m0;    }    void output(){        cout<
        
         <<' '<
         
          <<'\n'<
          
           <<' '<
           
            <<'\n'; }}tree[maxn];int n,m,T,a[maxn];void build(int rt,int l,int r){ if (l==r){ tree[rt]=Mat(1,a[l],1,0); return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); tree[rt]=tree[rt<<1|1]*tree[rt<<1];}Mat query(int rt,int l,int r,int L,int R){ if (L<=l && R>=r) return tree[rt]; int mid=(l+r)>>1; Mat tot(1,0,0,1); if (R> mid) tot=query(rt<<1|1,mid+1,r,L,R); if (L<=mid) tot=tot*query(rt<<1,l,mid,L,R); return tot;}int main(){ int x,y; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) scanf("%d",&a[i]); build(1,1,n); while (m--) { scanf("%d%d",&x,&y); if (y==x || y==x+1){ if (y==x) printf("%d\n",a[x]); else printf("%d\n",a[x+1]); continue; } Mat tmp=query(1,1,n,x+2,y); /* cout<<" ans Mat is : \n"; tmp.output(); cout<<" ........... the end of Mat."; */ printf("%d\n",(int)((tmp.f[0][0]*a[x+1]+tmp.f[0][1]*a[x])%mod)); } } return 0;}