本文主要是介绍zoj-3772-Calculate the Function-线段树+矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
之前板刷了很多的矩阵的题目。结果心中就有了一个很错误的想法。
就是矩阵的题目都是用来高次幂运算的。
今天看了这道题目，一开始感觉是矩阵，后来看看了，感觉不是矩阵，就放弃了。
后来放学的时候，SCF跟我说这道题目是线段树+矩阵。
我就又开始想了这道题目。
后来仔细想了想发现，原来是线段树预处理矩阵，然后每次询问O（log(n)）。
又学到了一招，真棒
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define LL long long
#define MOD 1000000007
struct matrix
{LL mat[3][3];
}A[110000],B;
struct list
{matrix a;int l;int r;
}node[110000*4];
matrix mul(matrix a,matrix b)
{matrix c;int i,j,k;for(i=1;i<=2;i++){for(j=1;j<=2;j++){c.mat[i][j]=0;for(k=1;k<=2;k++){c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];}c.mat[i][j]=c.mat[i][j]%MOD;}}return c;
}
matrix build(int l,int r,int st)
{if(l==r){node[st].l=l;node[st].r=r;node[st].a=A[l];return node[st].a;}matrix a,b;int mid=(l+r)/2;a=build(l,mid,st*2);b=build(mid+1,r,st*2+1);node[st].l=l;node[st].r=r;node[st].a=mul(b,a);return node[st].a;
}
matrix ans(int x,int y,int st)
{int l=node[st].l;int r=node[st].r;if(x<=l&&r<=y){return node[st].a;}if(x>r||y<l){matrix a;a.mat[1][1]=1;a.mat[1][2]=0;a.mat[2][2]=1;a.mat[2][1]=0;return a;}int mid=(l+r)/2;if(y<=mid)return ans(x,y,st*2);else if(x>mid)return ans(x,y,st*2+1);else{return mul(ans(x,y,st*2+1),ans(x,y,st*2));}
}
void qus(int x,int y)
{if(x==y||x==y-1){cout<<A[y].mat[1][2]<<endl;return;}matrix C;B.mat[1][1]=A[x+1].mat[1][2];B.mat[1][2]=0;B.mat[2][1]=A[x].mat[1][2];B.mat[2][2]=0;C=ans(x+2,y,1);C=mul(C,B);cout<<C.mat[1][1]<<endl;
}
int main()
{int T,x,n,m,i,y;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&x);A[i].mat[1][1]=1;A[i].mat[1][2]=x;A[i].mat[2][1]=1;A[i].mat[2][2]=0;}build(1,n,1);while(m--){scanf("%d%d",&x,&y);qus(x,y);}}return 0;
}这篇关于zoj-3772-Calculate the Function-线段树+矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
