一道纯粹的码力 + 卡常题。
前置
矩阵乘法，线段树。
分析
线段树存矩阵。
构造迭代矩阵：
\[\begin{pmatrix}f_i&f_{i-1}\end{pmatrix}\times\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}f_{i+1}&f_{i}\end{pmatrix}
\]
\]
\[\begin{pmatrix}f_i&f_{i-1}\end{pmatrix}\times\begin{pmatrix}0&1\\1&-1\end{pmatrix}=\begin{pmatrix}f_{i-1}&f_{i-2}\end{pmatrix}
\]
\]
另外矩阵乘法满足分配律，于是父结点矩阵为子结点矩阵之和。
然后就很清楚了。
先把要用的矩阵处理出来。
\(add\) 操作就是直接乘。
\(set\) 操作就直接覆盖即可。
两个标记 \(add\) 和 \(set\)，维护一下即可。
卡常
能用位运算尽量位运算。
快速幂不要递归求。
存矩阵不要用 \(a[2][2]\)，用 \(a,b,c,d\) 分别表示矩阵的四项。
\(a,b,c,d\) 不要开 \(longlong\)，考虑取模 \(10^9+7\)，矩阵加法不会溢出，矩阵乘法先转 \(longlong\) 再取模，要快很多。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define ri register int
const int N = 5e5 + 10, MOD = 1e9 + 7;
inline LL read () {
LL num = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') num = num * 10 + (c ^ 48), c = getchar();
return num * f;
}
int mod (int x) {
return (x % MOD + MOD) % MOD;
}
struct matrix {
int a, b, c, d;
void clear () {
a = b = c = d = 0;
}
friend matrix operator + (const matrix &x, const matrix &y) {
matrix ans;
ans.a = mod(x.a + y.a);
ans.b = mod(x.b + y.b);
ans.c = mod(x.c + y.c);
ans.d = mod(x.d + y.d);
return ans;
}
friend matrix operator * (const matrix &x, const matrix &y) {
matrix ans;
ans.a = mod(1ll * x.a * y.a % MOD + 1ll * x.b * y.c % MOD);
ans.b = mod(1ll * x.a * y.b % MOD + 1ll * x.b * y.d % MOD);
ans.c = mod(1ll * x.c * y.a % MOD + 1ll * x.d * y.c % MOD);
ans.d = mod(1ll * x.c * y.b % MOD + 1ll * x.d * y.d % MOD);
return ans;
}
};
const matrix st = (matrix){1, 0, 0, 1}, fibnxt = (matrix){1, 1, 1, 0}, fib = (matrix){1, 1, 0, 0}, fibpre = (matrix){0, 1, 1, -1};
matrix mat_qpow (matrix x, LL b) {
matrix res = st;
while (b) {
if (b & 1) res = res * x;
b >>= 1; x = x * x;
}
return res;
}
int n, m;
LL a[N];
struct node {
int l, r, cset;
matrix mat, add, sett;
}tree[N << 2];
inline void push_up (int p) {
tree[p].mat = tree[p << 1].mat + tree[p << 1 | 1].mat;
}
inline void update (int p, matrix x) {
if (!tree[p].cset) tree[p].add = tree[p].add * x;
else tree[p].sett = tree[p].sett * x;
tree[p].mat = tree[p].mat * x;
return;
}
inline void push_down (int p) {
if (tree[p].cset) {
int ll = tree[p << 1].r - tree[p << 1].l + 1; int lr = tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1;
tree[p << 1].add = tree[p << 1 | 1].add = st;
tree[p << 1].sett = tree[p << 1 | 1].sett = tree[p].sett;
tree[p << 1].mat = (matrix){ll, 0, 0, ll} * tree[p].sett;
tree[p << 1 | 1].mat = (matrix){lr, 0, 0, lr} * tree[p].sett;
tree[p << 1].cset = tree[p << 1 | 1].cset = 1;
tree[p].cset = 0;
}
else {
update(p << 1, tree[p].add); update(p << 1 | 1, tree[p].add);
tree[p].add = st;
}
}
void build (int p, int l, int r) {
tree[p].l = l, tree[p].r = r; tree[p].add = st;
if (l == r) {
tree[p].mat = fib * mat_qpow(fibnxt, a[l] - 1);
return;
}
int mid = (l + r) >> 1;
build (p << 1, l, mid); build (p << 1 | 1, mid + 1, r);
push_up(p);
}
void add (int p, int l, int r, matrix x) {
int tl = tree[p].l, tr = tree[p].r;
if (tl >= l && tr <= r) {
update(p, x);
return;
}
push_down(p);
int mid = (tl + tr) >> 1;
if (l <= mid) add (p << 1, l, r, x);
if (r > mid) add (p << 1 | 1, l, r, x);
push_up(p);
}
void sett (int p, int l, int r, matrix x) {
int tl = tree[p].l, tr = tree[p].r;
if (tl >= l && tr <= r) {
tree[p].cset = 1;
int ll = tr - tl + 1;
tree[p].mat = (matrix){ll, 0, 0, ll} * x;
tree[p].sett = x;
tree[p].add = st;
return;
}
push_down(p);
int mid = (tl + tr) >> 1;
if (l <= mid) sett (p << 1, l, r, x);
if (r > mid) sett (p << 1 | 1, l, r, x);
push_up(p);
}
int stk[N << 4], ed;
matrix query (int p, int l, int r) {
int tl = tree[p].l, tr = tree[p].r;
if (tl >= l && tr <= r) return tree[p].mat;
push_down(p);
int mid = (tl + tr) >> 1;
matrix res; res.clear();
if (l <= mid) res = res + query (p << 1, l, r);
if (r > mid) res = res + query (p << 1 | 1, l, r);
return res;
}
int main () {
// freopen("data10.in", "r", stdin);
// freopen("data10.ans", "w", stdout);
n = read();
for (ri i = 1;i <= n;++i) a[i] = read();
build (1, 1, n);
m = read();
while (m--) {
int op = read(), l = read(), r = read(), x;
if (op == 1) {
x = read();
matrix mat;
if (x < 0) mat = mat_qpow(fibpre, -x);
else mat = mat_qpow(fibnxt, x);
add(1, l, r, mat);
}
else if (op == 2) {
x = read();
matrix mat = fib * mat_qpow(fibnxt, x - 1);
sett(1, l, r, mat);
}
else printf("%lld\n", query(1, l, r).b);
}
return 0;
}
