ZOJ 3772 Calculate the Function (線段樹 + 矩陣)

思路分析：

遺憾不知道矩陣的構造。線段樹上比較水的矩陣。。。

M[x] = [1 A[x]]
[1 0 ]

就有

[ F[R] ] = M[R] * M[R-1] * ... * M[L+2] * [F[L+1]]
[F[R-1]] [ F[L] ] 。

#include 
#include 
#include 
#include 
#define maxn 100005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define mod 1000000007
using namespace std;
typedef long long LL;

LL save[maxn];


struct Matrix
{
	LL data[2][2];
	Matrix()
	{
		memset(data,0,sizeof data);
	}
	Matrix operator * (const Matrix &a)
	{
		Matrix temp;

		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		for(int k=0;k<2;k++)
		temp.data[i][j] = ((data[i][k] * a.data[k][j]) + temp.data[i][j]) % mod;

		return temp;
	}
}tre[maxn<<2];


void pushup(int num)
{
    tre[num]=tre[num<<1|1]*tre[num<<1];
}

void build(int num,int s,int e)
{
    if(s==e)
    {
        tre[num].data[0][0]=1;
        tre[num].data[0][1]=save[s];
        tre[num].data[1][0]=1;
        tre[num].data[1][1]=0;
        return ;
    }
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
    pushup(num);
}

Matrix query(int num,int s,int e,int l,int r)
{
    if(l<=s && r>=e)
    {
        return tre[num];
    }
    int mid=(s+e)>>1;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else return query(rson,l,r)*query(lson,l,r);//順序  attention!
}

int main()
{
    int T;
    int n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++)scanf("%lld",&save[i]);
        build(1,1,n);
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);

            if(r-l<2)printf("%d\n",save[r]);
            else
            {
                Matrix temp=query(1,1,n,l+2,r);
                LL ans=(temp.data[0][0]*save[l+1]+temp.data[0][1]*save[l])%mod;
                printf("%lld\n",ans);
            }
        }
    }
	return 0;
}