http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5235
这种题目居然没想到，一开始往矩阵快速幂想去了，因为之前跪了太多矩阵快速幂，后来就。。哎，擦。怎么没想到就是个线段树呢
因为1 A[x] * A[x-1] 这个是很容易推出的，比赛的时候看到这个就想那个快速幂去了，根本没往线段树上想，其实用线段树存储前面的矩阵，得到一个询问
1 0 A[x-2]
L R，则访问 L+2 ,R的矩阵部分提取出来，再跟A[L] A[L+1]相乘就是结果了
则建树为 nlogn，访问为mlogn，由于n和m都在10^5，所以可以承受
要注意的是矩阵不满足交换律，在这个线段树里面矩阵相乘的时候必须从大的到小的来乘。
#include <iostream> #include <cstdio> #include <cstring> #define lson rt<<1,l,mid #define rson (rt<<1|1),mid+1,r #define N 100010 #define ll unsigned long long using namespace std; ll A[N],n,m; const ll M=1000000007; struct MAT { ll mat[4][4]; }tree[N*3],E; void init(int rt,int x) { tree[rt].mat[0][0]=tree[rt].mat[1][0]=1; tree[rt].mat[0][1]=A[x]; tree[rt].mat[1][1]=0; } MAT operator *(MAT a,MAT b) { MAT c; memset(c.mat,0,sizeof (c.mat)); ll tmp; for (int i=0;i<2;i++) { for (int j=0;j<2;j++) { for (int k=0;k<2;k++) { tmp=(a.mat[i][k]*b.mat[k][j])%M; c.mat[i][j]+=tmp; if (c.mat[i][j]>M) c.mat[i][j]%=M; } } } return c; } void up(int l,int r,int rt) { tree[rt]=tree[rt<<1|1]*tree[rt<<1]; } void build(int rt,int l,int r) { if (l>=r) { init(rt,l); return; } int mid=(l+r)/2; build(lson); build(rson); up(l,r,rt); } void test(int rt,int l,int r) { cout<<l<<" lr "<<r<<":"<<endl; for (int i=0;i<2;i++) { for (int j=0;j<2;j++) { cout<<tree[rt].mat[i][j]<<" "; } cout<<endl; } cout<<endl; if (l>=r) { return; } int mid=(l+r)/2; test(lson); test(rson); } MAT query(int L,int R,int rt,int l,int r) { MAT c=E; if (L<=l && r<=R) { c=tree[rt]; return c; } int mid=(l+r)/2; if (R>mid) c=query(L,R,rson); if (L<=mid) c=c*query(L,R,lson); return c; } int main() { int t,a,b; scanf("%d",&t); memset(E.mat,0,sizeof E.mat); E.mat[1][1]=E.mat[0][0]=1; while (t--) { scanf("%llu%llu",&n,&m); for (ll i=1;i<=n;i++) scanf("%llu",&A[i]); build(1,1,n); //test(1,1,n); for (ll i=0;i<m;i++) { scanf("%d%d",&a,&b); if (a>b) swap(a,b); if (b-a<=1) { if (b==a) printf("%llu ",A[a]); else printf("%llu ",A[b]); continue; } MAT c; c=query(a+2,b,1,1,n); ll ans=((c.mat[0][0]*A[a+1])%M)+((c.mat[0][1]*A[a])%M); ans%=M; printf("%llu ",ans); } } return 0; }