http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5235
这道题需要构造矩阵：F(X)=F(X-1)+F(X-2)*A(X)转化为F(X)*A(X+2)+F(X+1)=F(X+2)，然后在构造矩阵
{1, A[x]} {F(x+1)} {F(X+2)}
{1, 0 }*{F(X) }={F(X+1)}
然后用线段数维护乘号左边的乘积；
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 101000
using namespace std;
const int mod=; int t,a[maxn*],n,m;
int l,r;
struct matrix
{
long long a[][];
}; struct node
{
int l;
int r;
matrix c;
} tree[maxn*]; matrix multi(matrix x,matrix y)
{
matrix temp;
for(int i=; i<=; i++)
{
for(int j=; j<=; j++)
{
temp.a[i][j]=;
for(int k=; k<=; k++)
{
temp.a[i][j]=(x.a[i][k]*y.a[k][j]+temp.a[i][j])%mod;
}
}
}
return temp;
} matrix build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
if(l==r)
{
tree[i].c.a[][]=;
tree[i].c.a[][]=a[l];
tree[i].c.a[][]=;
tree[i].c.a[][]=;
return tree[i].c;
}
int mid=(l+r)>>;
build(i<<,l,mid);
build(i<<|,mid+,r);
tree[i].c=multi(tree[i<<|].c,tree[i<<].c);
return tree[i].c;
} matrix search1(int i,int l,int r)
{
if(tree[i].l==l&&tree[i].r==r)
{
return tree[i].c;
}
int mid=(tree[i].l+tree[i].r)>>;
if(r<=mid)
{
return search1(i<<,l,r);
}
else if(l>mid)
{
return search1(i<<|,l,r);
}
else
{
return multi(search1(i<<|,mid+,r),search1(i<<,l,mid));
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
build(,,n);
while(m--)
{
scanf("%d%d",&l,&r);
if(r-l>=)
{
matrix tm,ans;
tm.a[][]=a[l+];
tm.a[][]=a[l];
ans=multi(search1(,l+,r),tm);
printf("%lld\n",ans.a[][]);
}
else printf("%d\n",a[r]%mod);
}
}
return ;
}