华南理工大学“三七互娱杯”程序设计竞赛（重现赛）B HRY and fibonacci
题目链接：https://ac.nowcoder.com/acm/contest/874/B
题目大意：
设 fib(i) 为第 i 项斐波那契数列：$$fib(0) = 0, fib(1) = 1, fib(i) = fib(i - 1) + fib(i - 2), i geq 2$$
利用 fib 序列定义 fic 和 fid 序列：$$fic(n) = sum_{i = 1}^{n} fib(i)$$ $$fid(n) = sum_{i = 1}^{n} fic(i)$$
现在给定序列 a1，a2……an。
再给出 2 种操作：
- 给定区间 [L, R]，对于所有$L leq i leq R$，执行 ai += x。
- 给定区间 [L, R]，计算$(sum_{i = L}^{R} fid(i)) \% (1e8 + 7)$，并输出。
分析：
先求 fic 的通项：
$$
egin{align*}
fic(n) - fic(n - 1) &= fib(n) \
&= fib(n - 1) + fib(n - 2) \
&= fib(1) + sum_{i = 1}^{n - 2} fib(i) \
&= fib(1) + fic(n - 2) \ \
fic(n) &= fic(n - 1) + fic(n - 2) + 1, fic(1) = 1, fic(2) = 2
end{align*}
$$
同理 fid 的通项为：
$$
fid(n) = fid(n - 1) + fid(n - 2) + n, fid(1) = 1, fid(2) = 3
$$
fid 的通项其实和 fib 差不多，他们都可以用矩阵快速幂的方法计算第 n 项。
构造如下矩阵 M：
$$
M = egin{bmatrix}
1 & 1 & 0 & 0 \
1 & 0 & 0 & 0 \
1 & 0 & 1 & 0 \
1 & 0 & 1 & 1 \
end{bmatrix}
$$
再构造如下矩阵 FID(i)：
$$
FID(i) = egin{bmatrix}
fid(i) & fid(i - 1) & i & 1
end{bmatrix}
$$
于是有：
$$
FID(n) = FID(n - 1) * M \
FID(n) = FID(1) * M^{n - 1}
$$
由于是区间操作，所以想到用线段树，线段树每个节点维护$sum_{i = L}^{R} FID(a_i)$。
由于 Mn 的最后一行恰好就是 FID(n)，因此线段树每个节点只要维护$sum_{i = L}^{R} M^{a_i}$即可。
最后说一下我做这道题的坎：
- 用vector存矩阵，结果超时。
- 用结构体封装线段树，结果超时，要拿到外面来。
- 用scanf输入，结果超时，因此用了快速输入函数 ri()。
- 常规线段树成段更新操作，就是要标懒惰标记然后 pushDown 的，结果超时，然后我取消 pushDown，直接把信息存在懒惰标记里，于是懒惰标记数组就成了线段树的对应参数辅助树，勉强过了。
代码如下：
1 #pragma GCC optimize("Ofast") 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0); 6 #define Rep(i,n) for (int i = 0; i < (n); ++i) 7 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 8 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 9 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) 10 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 11 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 12 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 13 14 #define pr(x) cout << #x << " = " << x << " " 15 #define prln(x) cout << #x << " = " << x << endl 16 17 #define LOWBIT(x) ((x)&(-x)) 18 19 #define ALL(x) x.begin(),x.end() 20 #define INS(x) inserter(x,x.begin()) 21 22 #define ms0(a) memset(a,0,sizeof(a)) 23 #define msI(a) memset(a,inf,sizeof(a)) 24 #define msM(a) memset(a,-1,sizeof(a)) 25 26 #define MP make_pair 27 #define PB push_back 28 #define ft first 29 #define sd second 30 31 template<typename T1, typename T2> 32 istream &operator>>(istream &in, pair<T1, T2> &p) { 33 in >> p.first >> p.second; 34 return in; 35 } 36 37 template<typename T> 38 istream &operator>>(istream &in, vector<T> &v) { 39 for (auto &x: v) 40 in >> x; 41 return in; 42 } 43 44 template<typename T1, typename T2> 45 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 46 out << "[" << p.first << ", " << p.second << "]" << " "; 47 return out; 48 } 49 50 inline int gc(){ 51 static const int BUF = 1e7; 52 static char buf[BUF], *bg = buf + BUF, *ed = bg; 53 54 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 55 return *bg++; 56 } 57 58 inline int ri(){ 59 int x = 0, f = 1, c = gc(); 60 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 61 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 62 return x*f; 63 } 64 65 typedef long long LL; 66 typedef unsigned long long uLL; 67 typedef pair< double, double > PDD; 68 typedef pair< int, int > PII; 69 typedef set< int > SI; 70 typedef vector< int > VI; 71 typedef vector< LL > VL; 72 typedef vector< VL > VVL; 73 typedef map< int, int > MII; 74 const double EPS = 1e-10; 75 const int inf = 1e9 + 9; 76 const LL mod = 1e8 + 7; 77 const int maxN = 1e5 + 7; 78 const LL ONE = 1; 79 const LL evenBits = 0xaaaaaaaaaaaaaaaa; 80 const LL oddBits = 0x5555555555555555; 81 82 struct Matrix{ 83 const static int sz = 4; 84 LL mat[sz][sz]; 85 86 Matrix() { clear(); } 87 Matrix(const VVL &x) { 88 Rep(i, sz) { 89 Rep(j, sz) { 90 mat[i][j] = x[i][j]; 91 } 92 } 93 } 94 95 // x * 单位阵 96 inline void E(int x = 1) { 97 //assert(row == col); 98 clear(); 99 Rep(i, sz) mat[i][i] = x; 100 } 101 102 inline Matrix operator+ (const Matrix &x) { 103 //assert(row == x.row && col == x.col); 104 Matrix ret; 105 Rep(i, sz) { 106 Rep(j, sz) { 107 ret.mat[i][j] = (mat[i][j] + x.mat[i][j]) % mod; 108 } 109 } 110 return ret; 111 } 112 113 inline Matrix operator* (const Matrix &x) { 114 //assert(col == x.row); 115 Matrix ret; 116 Rep(k, sz) { 117 Rep(i, sz) { 118 if(mat[i][k] == 0) continue; 119 Rep(j, sz) { 120 ret.mat[i][j] = (ret.mat[i][j] + mat[i][k] * x.mat[k][j]) % mod; 121 } 122 } 123 } 124 return ret; 125 } 126 127 inline Matrix operator*= (const Matrix &x) { return *this = *this * x; } 128 inline Matrix operator+= (const Matrix &x) { return *this = *this + x; } 129 130 inline void clear() { ms0(mat); } 131 132 inline void print() { 133 Rep(i, sz) { 134 Rep(j, sz) { 135 cout << mat[i][j] << " "; 136 } 137 cout << endl; 138 } 139 } 140 }; 141 142 Matrix base[65]; 143 const Matrix M(VVL( {{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 0, 1, 0}, {1, 0, 1, 1}} )); 144 145 void initBase() { 146 base[1] = M; 147 For(i, 2, 64) { 148 base[i] = base[i - 1] * base[i - 1]; 149 } 150 } 151 152 // 矩阵快速幂，计算M^y 153 inline Matrix mat_pow_mod(LL y) { 154 Matrix ret; 155 ret.E(); 156 int tmp = 1; 157 while(y){ 158 if(y & 1) ret *= base[tmp]; 159 ++tmp; 160 y >>= 1; 161 } 162 return ret; 163 } 164 165 int n, Q; 166 167 #define lson l , mid , rt << 1 168 #define rson mid + 1 , r , rt << 1 | 1 169 Matrix st[maxN << 2]; 170 Matrix lazy[maxN << 2]; 171 172 inline void pushUp(int rt) { 173 st[rt] = (st[rt << 1] + st[rt << 1 | 1]) * lazy[rt]; 174 } 175 176 inline void build(int l, int r, int rt) { 177 lazy[rt].E(); 178 if(l >= r) { 179 int a = ri(); 180 st[rt] = mat_pow_mod(a); 181 return; 182 } 183 int mid = (l + r) >> 1; 184 build(lson); 185 build(rson); 186 pushUp(rt); 187 } 188 189 inline void update(int L, int R, Matrix x, int l, int r, int rt) { 190 if(L <= l && r <= R) { 191 lazy[rt] *= x; // 记录懒惰标记，不再往下更新 192 st[rt] *= x; 193 return; 194 } 195 int mid = (l + r) >> 1; 196 if(L <= mid) update(L, R, x, lson); 197 if(R > mid) update(L, R, x, rson); 198 pushUp(rt); 199 } 200 201 // 查询区间[L, R]和 202 inline Matrix query(int L, int R, int l, int r, int rt) { 203 if(L <= l && r <= R) return st[rt]; 204 int mid = (l + r) >> 1; 205 Matrix ret; 206 if(L <= mid) ret += query(L, R, lson); 207 if(R > mid) ret += query(L, R, rson); 208 return ret * lazy[rt]; 209 } 210 211 int main(){ 212 //INIT(); 213 initBase(); 214 n = ri(); 215 build(1, n, 1); 216 217 Q = ri(); 218 Rep(i, Q) { 219 int mode, l, r; 220 mode = ri(); 221 l = ri(); 222 r = ri(); 223 if(mode == 1) update(l, r, mat_pow_mod(ri()), 1, n, 1); 224 else printf("%lld ", query(l, r, 1, n, 1).mat[3][0]); 225 } 226 return 0; 227 }