ZJU 3772 Calculate the Function

对矩阵有了更深的理解，遇到加法和乘法的线性变换就应该想到矩阵。
原题本质相当于求在一个给定区间内的一连串矩阵的乘积，需要用到逆矩阵和模运算中逆元的知识。
矩阵乘法不满足交换律，所以需要特别注意相乘顺序（不要颠倒）。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define OUT(x) cerr << #x << ": " << (x) << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long LL;

const int MOD = 1000 * 1000 * 1000 + 7;

typedef vector< vector<int> > MTRX;
MTRX make(int a, int b, int c, int d) {
    MTRX tmp(2, vector<int>(2));
    tmp[0][0] = a;
    tmp[0][1] = b;
    tmp[1][0] = c;
    tmp[1][1] = d;
    return tmp;
}

MTRX one() {
    return make(1, 0, 0, 1);
}

MTRX zero() {
    return make(0, 0, 0, 0);
}

MTRX operator*(const MTRX& a, const MTRX& b) {
    MTRX c = zero();
    REP(i, 2) REP(j, 2) REP(k, 2) {
        c[i][j] = (c[i][j] + (LL)a[i][k] * b[k][j]) % MOD;
    }
    return c;
}

int power(int x, int n) {
    int r = 1;
    while (n) {
        if (n & 1) r = (LL)r * x % MOD;
        if (n >>= 1) x = (LL)x * x % MOD;
    }
    return r;
}

int main() {
    int T, N, M;
    vector<int> A, revA;
    vector<MTRX> orig, reverse;

    scanf("%d", &T);
    REP(tid, T) {
        scanf("%d%d", &N, &M);
        A.resize(N + 1);
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &A[i]);
        }
        revA.resize(N + 1);
        for (int i = 1; i <= N; ++i) {
            revA[i] = power(A[i], MOD - 2);
        }

        orig.clear();
        orig.push_back(one());
        for (int i = 1; i <= N; i++) {
            orig.push_back(orig.back() * make(0, A[i], 1, 1));
        }

        reverse.clear();
        reverse.push_back(one());
        for (int i = 1; i <= N; i++) {
            reverse.push_back(make((-revA[i] + MOD) % MOD, 1, revA[i], 0) * reverse.back());
        }

        while (M--) {
            int L, R;
            scanf("%d%d", &L, &R);
            if (L + 2 <= R) {
                MTRX ans = make(A[L], A[L + 1], 0, 0) * reverse[L + 1] * orig[R];
                printf("%d\n", ans[0][1]);
            } else {
                printf("%d\n", A[R]);
            }
        }
    }
    return 0;
}