题目链接
分析：矩阵快速幂+线段树 斐波那契数列的计算是矩阵快速幂的模板题，这个也没什么很多好解释的，学了矩阵快速幂应该就知道的东西= =这道题比较巧妙的在于需要用线段树来维护矩阵，达到快速查询区间斐波那契数列和的目的。这道题极为卡常数，我TLE了不知道多少发，才在赛后过了这道题。
我尝试下来，发现矩阵乘法的写法极为重要，我就是因为用了三层循环来写矩阵乘法导致了悲剧的TLE，一直卡在了第17组数据。我百度了网上别的矩阵快速幂的写法才过了这道题。 还有涨智识的地方是不要随意memset。我原来的矩阵快速幂的模板里面在构造函数的时候会memset元素为0，去掉了这句话，代码快了1s。。。
毕竟萌新还是太嫩，没有很多老司机的经验。。貌似bc87场的第三题也是卡了memset的常数。我也TLE了一发。
/*****************************************************/ // #pragma comment(linker, "/STACK:1024000000,1024000000") #include <map> #include <set> #include <ctime> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define offcin ios::sync_with_stdio(false) #define sigma_size 26 #define lson l,m,v<<1 #define rson m+1,r,v<<1|1 #define slch v<<1 #define srch v<<1|1 #define sgetmid int m = (l+r)>>1 #define LL long long #define ull unsigned long long #define mem(x,v) memset(x,v,sizeof(x)) #define lowbit(x) (x&-x) #define bits(a) __builtin_popcount(a) #define mk make_pair #define pb push_back #define fi first #define se second const int INF = 0x3f3f3f3f; const LL INFF = 1e18; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-9; const LL mod = 1e9+7; const int maxmat = 10; const ull BASE = 31; /*****************************************************/ const int maxn = 1e5 + 5; int a[maxn]; int N, M; struct Mat { int N; LL a[2][2]; Mat (int _n = 2) : N(_n) { //这里我原来会memset } void Debug() { for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) cout<<a[i][j]<<" "; cout<<endl; } } // Mat operator *(const Mat &rhs) const { //悲剧的三重循环写法 // Mat c(N); // for (int i = 0; i < N; i ++) // for (int k = 0; k < N; k ++) { // if (!a[i][k]) continue; // for (int j = 0; j < N; j ++) // c.a[i][j] = (c.a[i][j] + a[i][k] * rhs.a[k][j] % mod) % mod; // } // return c; // } Mat operator *(const Mat &rhs) const { //同时也能能够避免三重循环需要先memset矩阵的时间复杂度 Mat ret; ret.a[0][0] = (1ll * a[0][0] * rhs.a[0][0] + 1ll * a[0][1] * rhs.a[1][0]) % mod; ret.a[1][0] = ret.a[0][1] = (1ll * a[0][0] * rhs.a[0][1] + 1ll * a[0][1] * rhs.a[1][1]) % mod; ret.a[1][1] = (1ll * a[1][0] * rhs.a[0][1] + 1ll * a[1][1] * rhs.a[1][1]) % mod; return ret; } Mat operator +(const Mat &rhs) const { Mat c(N); for (int i = 0; i < N; i ++) for (int j = 0; j < N; j ++) c.a[i][j] = (a[i][j] + rhs.a[i][j]) % mod; return c; } }; Mat E(2), F(2); void init() { E.a[0][0] = E.a[1][1] = 1; F.a[0][0] = F.a[0][1] = F.a[1][0] = 1; } Mat qpow(Mat A, LL b) { Mat c = E; while (b > 0) { if (b & 1) c = A * c; b >>= 1; A = A * A; } return c; } Mat seg[maxn << 2], col[maxn << 2]; bool add[maxn << 2]; void PushUp(int v) { seg[v] = seg[slch] + seg[srch]; } void PushDown(int v, int m) { if (!add[v]) return; col[slch] = col[slch] * col[v]; col[srch] = col[srch] * col[v]; seg[slch] = seg[slch] * col[v]; seg[srch] = seg[srch] * col[v]; add[slch] = add[srch] = true; col[v] = E; add[v] = false; } void build(int l, int r, int v) { col[v] = E; if (l == r) { int k; scanf("%d", &k); seg[v] = qpow(F, k - 1); } else { sgetmid; build(lson); build(rson); PushUp(v); } } void update(int L, int R, int x, int l, int r, int v) { if (L <= l && r <= R) { Mat temp = qpow(F, x); seg[v] = seg[v] * temp; col[v] = col[v] * temp; add[v] = true; return; } sgetmid; PushDown(v, r - l + 1); if (L <= m) update(L, R, x, lson); if (R > m) update(L, R, x, rson); PushUp(v); } LL query(int L, int R, int l, int r, int v) { if (L <= l && r <= R) return seg[v].a[0][0]; sgetmid; PushDown(v, r - l + 1); LL ans = 0; if (L <= m) ans = (ans + query(L, R, lson)) % mod; if (R > m) ans = (ans + query(L, R, rson)) % mod; return ans; } int main(int argc, char const *argv[]) { cin>>N>>M; init(); mem(add, false); build(1, N, 1); while (M --) { int op; scanf("%d", &op); if (op == 1) { int l, r, x; scanf("%d%d%d", &l, &r, &x); update(l, r, x, 1, N, 1); } else { int l, r; scanf("%d%d", &l, &r); printf("%I64d\n", query(l, r, 1, N, 1)); } } return 0; }