Description
You are given a list of numbersA1A2..ANandMqueries. For the i-th query:
You task is to calculateFi(Ri)for each query. Because the answer can be very large, you should output the remainder of the answer divided by 1000000007.
Input
There are multiple test cases. The first line of input is an integerTindicates the number of test cases. For each test case:
The first line contains two integersN,M(1 <=N,M<= 100000). The second line containsNintegersA1A2..AN(1 <=Ai<= 1000000000).
The nextMlines, each line is a query with two integer parametersLi,Ri(1 <=Li<=Ri<=N).
Output
For each test case, output the remainder of the answer divided by 1000000007.
Sample Input
14 71 2 3 41 11 21 31 42 43 44 4
Sample Output
125131144
题意：给你一段序列，，每次问你一段区间构造的数列的最后一项。
分析：这题显然不能暴力，正确做法就是将矩阵套到线段树里，每个节点
里存的都是一个矩阵，然后求区间pushup时候利用矩阵乘法乘一次就行了
注意矩阵相乘的顺序。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<set>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )const int INF=0x3f3f3f3f;typedef long long LL;const int mod=1e9+7;const int maxn=1e5+100;LL a[maxn];int t,n,m;struct Matrix{LL mat[2][2];Matrix(){};Matrix(int x){mat[0][0]=mat[1][0]=1;mat[0][1]=x;mat[1][1]=0;}}A[maxn<<2];Matrix mult(Matrix m1,Matrix m2){Matrix ans;for(int i=0;i<2;i++){for(int j=0;j<2;j++){ans.mat[i][j]=0;for(int k=0;k<2;k++)ans.mat[i][j]=(ans.mat[i][j]+m1.mat[i][k]*m2.mat[k][j])%mod;}}return ans;}void build(int rs,int l,int r){if(l==r){A[rs]=Matrix(a[l]);return ;}int mid=(l+r)>>1;build(rs<<1,l,mid);build(rs<<1|1,mid+1,r);A[rs]=mult(A[rs<<1|1],A[rs<<1]);}Matrix query(int x,int y,int l,int r,int rs){if(l>=x&&r<=y)return A[rs];int mid=(l+r)>>1;if(y<=mid) return query(x,y,l,mid,rs<<1);if(x>mid) return query(x,y,mid+1,r,rs<<1|1);return mult(query(mid+1,y,mid+1,r,rs<<1|1),query(x,mid,l,mid,rs<<1));}int main(){int l,r;scanf("%d",&t);while(t–){Matrix hehe;scanf("%d%d",&n,&m);REPF(i,1,n)scanf("%lld",&a[i]);build(1,1,n);while(m–){scanf("%d%d",&l,&r);if(r-l<=1)printf("%lld\n",a[r]);else{hehe=query(l+2,r,1,n,1);LL ans=(hehe.mat[0][0]*a[l+1]%mod+hehe.mat[0][1]*a[l]%mod)%mod;printf("%lld\n",ans);}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你怎么样对待别人被人就怎么样对待你。
