?Calculate the Function

Problem's Link: ??http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3772

---

?

Mean:?

略?

analyse:

簡單的線段樹維護矩陣。

矩陣乘法的結合律（a * b * c == a * (b * c)），注意矩陣乘法不滿足分配率（a *b != b * a）。

?

令 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] ]?

?

線段樹節點維護上邊等式右邊前n - 1項的乘值(假設等式右邊有n項)。每次詢問O（log(n)）。

?

Time complexity: O(n*logn)

?

Source code:?

?

/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-25-20.57 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std;const int MAXN = 100100; const int MOD = 1000000007; struct Mat {long long m[2][2];Mat(){memset(m, 0, sizeof(m));}Mat operator * (const Mat &b){Mat temp;for(int i = 0; i < 2; i++)for(int j = 0; j < 2; j++)for(int k = 0; k < 2; k++)temp.m[i][j] = ((m[i][k] * b.m[k][j]) + temp.m[i][j]) % MOD;return temp;} };struct Node {int l, r;Mat mat; }; Node node[MAXN << 2]; int a[MAXN];void Build(int rt, int l, int r) {int m;node[rt].l = l;node[rt].r = r;if(l == r){node[rt].mat.m[0][0] = 1;node[rt].mat.m[0][1] = a[l];node[rt].mat.m[1][0] = 1;node[rt].mat.m[1][1] = 0;}else{m = (l + r) >> 1;Build(rt << 1, l, m);Build(rt << 1 | 1, m + 1, r);node[rt].mat = node[rt << 1 | 1].mat * node[rt << 1].mat;//注意順序 }} Mat Query(int rt, int ql, int qr) {int m;if(ql == node[rt].l && node[rt].r == qr)return node[rt].mat;else{m = (node[rt].l + node[rt].r) >> 1;if(qr <= m)return Query(rt << 1, ql, qr);else if(ql > m)return Query(rt << 1 | 1, ql, qr);elsereturn Query(rt << 1 | 1, m + 1, qr) * Query(rt << 1, ql, m);//注意順序 } } int T, n, m, ql, qr;int main() {scanf("%d", &T);while(T--){Mat res, f;scanf("%d%d",&n, &m);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);Build(1, 1, n);for(int i = 1; i<= m; i++){scanf("%d%d", &ql, &qr);if(qr - ql >= 2){f.m[0][0] = a[ql + 1];f.m[1][0] = a[ql];res = Query(1, ql + 2, qr) * f;printf("%d\n", res.m[0][0]);}elseprintf("%d\n", a[qr]);}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/crazyacking/p/4529012.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的线段树 + 矩阵 --- ZOJ 3772 Calculate the Function的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。