华南理工大学“三七互娱杯”程序设计竞赛（重现赛）B HRY and fibonacci

  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 << "]" << "\n";
 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\n", query(l, r, 1, n, 1).mat[3][0]);
225     }
226     return 0;
227 }