[原创]ZOJ 3772 Calculate the Function [线段树+矩阵乘法]【思维？】

2017-03-21 08:02:33 Tabris_ 阅读数：558

博客爬取于2020-06-14 22:41:09
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/64432631

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3772
————————————————————————————————————————————
Calculate the Function

Time Limit: 2 Seconds Memory Limit: 65536 KB

You are given a list of numbers A1 A2 … AN and M queries. For the i-th query:

The query has two parameters Li and Ri.
The query will define a function Fi(x) on the domain [Li, Ri] ∈ Z.
Fi(Li) = ALi
Fi(Li + 1) = A(Li + 1)
for all x >= Li + 2, Fi(x) = Fi(x - 1) + Fi(x - 2) × Ax

You task is to calculate Fi(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 integer T indicates the number of test cases. For each test case:

The first line contains two integers N, M (1 <= N, M <= 100000). The second line contains N integers A1 A2 … AN (1 <= Ai <= 1000000000).

The next M lines, each line is a query with two integer parameters Li, Ri (1 <= Li <= Ri <= N).

Output
For each test case, output the remainder of the answer divided by 1000000007.

Sample Input
1
4 7
1 2 3 4
1 1
1 2
1 3
1 4
2 4
3 4
4 4

Sample Output
1
2
5
13
11
4
4
————————————————————————————————————————————
题目大意:

给一段序列 对于每一段查询区间,序列的值为
Fi(x)={ ALix=LiALi+1x=Li+1Fi(x−1)+Fi(x−2)×Axx>=Li+2Fi(x) = \left\{\begin{array}{rcl}\ A_{Li} &&x=Li\\ A_{Li+1} &&x=Li+1 \\Fi(x - 1) + Fi(x - 2) × Ax && x >= Li + 2\end{array}\right.

解题思路:

训练的时候一直想 会有什么技巧/黑科技一类的将其转化成一个O(1)查询的问题

最后还是没有想出来,最后看了题解 才知道这是一个线段树+矩阵乘法的

跟那个博主一样进入了 矩阵一定是求高次幂的误区

这题就是fibonacci数列
$\left[\begin{array}{cc}\ Fi(x + 1) && Fi(x) \\ 0 &&0 \end{array}\right] \times \left[\begin{array}{cc}
\ 1&& 1\\ A_x+2 &&0 \end{array}\right]=\left[\begin{array}{cc}\ Fi(x + 2) && Fi(x+1) \ 0 &&0 \end{array}\right] $

我们只要用线段树处理出一段区间的右矩阵的乘积就好了

查询就变成了O((log⁡2(n)∗2)3)O((\log_{2}(n)*2)^3)

附本题代码
———————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# include <bits/stdc++.h>
using namespace std;
typedef long long int LL;

const int N   = 100000+7;
const int M   = 2;
const int MOD = 1e9+7;

struct Matrix{
    LL m[M][M];
    void clear0(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=0;
    }
    void clearE(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=(i==j);
    }

};

Matrix operator * (Matrix a,Matrix b){
    Matrix c;
    c.clear0();

    for(int k=0;k<M;k++){
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++){
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    }
    return c;
}

struct node{
    Matrix a;
    int l,r;
}tree[N<<2];
int w[N];

# define ll (rt<<1)
# define rr (rt<<1|1)
# define mid  ((r+l)>>1)

void pushup(int rt){
    tree[rt].a=tree[ll].a*tree[rr].a;
}

void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r){
        tree[rt].a.m[0][0]=1   ,tree[rt].a.m[0][1]=1;
        tree[rt].a.m[1][0]=w[l],tree[rt].a.m[1][1]=0;
        return ;
    }
    build(ll,l,mid);
    build(rr,mid+1,r);
    pushup(rt);
}

Matrix query(int rt,int L,int R){
    if(L<=tree[rt].l&&tree[rt].r<=R)   return tree[rt].a;

    Matrix ans,b;ans.clearE();
    int md = (tree[rt].l+tree[rt].r)>>1;
    if(L<=md) b=query(ll,L,R),ans=ans*b;
    if(R> md) b=query(rr,L,R),ans=ans*b;
    return ans;
}

Matrix a,b;

void ask(int l,int r){
    if(l==r||l+1==r){
        printf("%d\n",w[r]);
        return ;
    }

    a.m[0][0]=w[l+1],a.m[0][1]=w[l];
    a.m[1][0]=0     ,a.m[1][1]=0;
    b=query(1,l+2,r);
    b=a*b;
    printf("%d\n",b.m[0][0]);

    return  ;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&w[i]);
        }

        build(1,1,n);

        int l,r;
        while(m--){
            scanf("%d%d",&l,&r);
            ask(l,r);
        }
    }
    return 0;
}