http://codeforces.com/contest/719/problem/E
题目大意：给你一串数组a，a[i]表示第i个斐波那契数列，有如下操作
①对[l,r]区间+一个val ②求出[l,r]区间的和。
定义区间的和为该区间内每个a[i]所对应的斐波那契数列的和。
思路：线段树保存区间val，和区间更新，用矩阵快速幂求解复杂度是m*logn*logk
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") const int maxn = 1e5 + 5; const LL mod = 1e9 + 7; struct Node{ LL mat[2][2]; void reset(){memset(mat, 0, sizeof(mat));} void getone(){ reset(); mat[0][0] = mat[1][1] = 1; } }; inline Node mul(Node A, Node B){ Node ans; ans.reset(); for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) ans.mat[i][j] = (ans.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % mod; return ans; } inline Node add(Node a, Node b){ Node ans; ans.reset(); for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) ans.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % mod; return ans; } inline Node kpow(LL k){ Node ans; ans.reset(); ans.mat[0][0] = ans.mat[1][1] = 1; Node A; A.mat[0][0] = A.mat[1][0] = A.mat[0][1] = 1; A.mat[1][1] = 0; while (k){ if (k & 1) ans = mul(ans, A); A = mul(A, A); k >>= 1; } return ans; } struct Mytree{ Node sum; Node lazyk; }tree[maxn << 2]; int n, m; inline void push_up(int o){ int lb = o << 1, rb = o << 1 | 1; tree[o].sum = add(tree[lb].sum, tree[rb].sum); } void build_tree(int l, int r, int o){ if (l == r){ LL k; scanf("%lld", &k); tree[o].sum = kpow(k); tree[o].lazyk.getone(); return ; } tree[o].sum.reset(); tree[o].lazyk.getone(); int mid = (l + r) / 2; if (l <= mid) build_tree(l, mid, o << 1); if (r > mid) build_tree(mid + 1, r, o << 1 | 1); push_up(o); } inline void push_down(int o){ int lb = o << 1, rb = o << 1 | 1; tree[lb].sum = mul(tree[lb].sum, tree[o].lazyk); tree[lb].lazyk = mul(tree[lb].lazyk, tree[o].lazyk); tree[rb].sum = mul(tree[rb].sum, tree[o].lazyk); tree[rb].lazyk = mul(tree[rb].lazyk, tree[o].lazyk); tree[o].lazyk.getone(); } void update(int l, int r, int ql, int qr, Node k, int o){ if (ql <= l && qr >= r){ tree[o].sum = mul(tree[o].sum, k); tree[o].lazyk = mul(tree[o].lazyk, k); return ; } int mid = (l + r) / 2; push_down(o); if (ql <= mid) update(l, mid, ql, qr, k, o << 1); if (qr > mid) update(mid + 1, r, ql, qr, k, o << 1 | 1); push_up(o); return ; } Node query(int l, int r, int ql, int qr, int o){ if (ql <= l && qr >= r){ return tree[o].sum; } push_down(o); Node ans; ans.reset(); int mid = (l + r) / 2; if (ql <= mid) ans = add(query(l, mid, ql, qr, o << 1), ans); if (qr > mid) ans = add(query(mid + 1, r, ql, qr, o << 1 | 1), ans); push_up(o); return ans; } int main(){ scanf("%d%d", &n, &m); build_tree(1, n, 1); for (int i = 0; i < m; i++){ int ty; scanf("%d", &ty); if (ty == 1){ int l, r; LL k; scanf("%d%d%lld", &l, &r, &k); update(1, n, l, r, kpow(k), 1); } else if (ty == 2){ int l, r; scanf("%d%d", &l, &r); Node ans = query(1, n, l, r, 1); printf("%lld ", ans.mat[1][0]); } } return 0; }