题目大意
给定一个长为 \(n\) 的序列 \(a\)，支持以下操作：
-
\(\forall i \in[l,r],a_i\gets a_i +x\)。
-
求 \(\left(\sum\limits_{i=l}^{r}F_{a_i}\right)\bmod (10^9+7)\)，其中 \(F\) 表示斐波那契数列，即有 \(F_1=1,F_2=1,\forall i>2,F_i=F_{i-1}+F_{i-2}\)。
思路分析
给出一种与现有题解完全不一样的方法。
我们都知道，斐波那契数列存在通项公式，即有：
\[F_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right)
\]
（通项公式的推导本文不再赘述。）
那么，我们就可以将斐波那契数列看成两个等比数列的差，我们只需要维护等比数列就可以了。
不难发现，我们可以用线段树维护等比数列的值的和，那么区间加就变成了区间乘，也就是说，我们只需要维护一颗支持区间求和，区间乘的线段树就行了，而这是容易做到的。
但问题出现了，我们的所有操作都是在模 \(10^9+7\) 意义下进行的，我们发现，\(5\) 是模 \(10^9+7\) 的二次非剩余，也就是说，我们找不到一个 \(x\in[0,10^9+7)\) 使得 \(x^2=5\)，那么这就意味着 \(\sqrt 5\) 无法直接参与模运算。
考虑扩域，我们将所有数表示为 \(A\sqrt 5+B\) 的形式，其中 \(A,B\) 都是正整数，可以直接参与模运算。那么我们只需要证明加法，减法，乘法和除 \(\sqrt 5\) 这四种运算均对该域封闭即可。
\[\begin{cases}
(A\sqrt 5 + B) + (C\sqrt 5 + D) = (A+C)\sqrt 5 + (B+D)\\
(A\sqrt 5 + B) - (C\sqrt 5 + D) = (A-C)\sqrt 5 + (B-D)\\
(A\sqrt 5 + B)\times (C\sqrt 5 + D)= (AD+BC)\sqrt 5 + (5AC+BD)\\
(A\sqrt 5 + B)\times \dfrac{1}{\sqrt 5} = (\dfrac{1}{5}B)\sqrt 5 + (A)\\
\end{cases}\]
因为 \(5\) 在模 \(10^9+7\) 意义下有逆元，因此我们证明了这四种运算对该域封闭。
那么我们就可以愉快的直接套通项公式和线段树解决这道题了。
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 200200, mod = 1000000007;
#define inf 0x3f3f3f3f
#define int long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
#define getchar() (p1 == p2 && (p2 = (p1 = BS) + fread(BS, 1, 1 << 16, stdin), p1 == p2) ?EOF : *p1 ++)
char BS[1 << 16], *p1 = BS, *p2 = BS;
template <typename Tp> void read(Tp &x){
x=0; bool f = 0; char ch = getchar();
while (ch > '9' || ch < '0') f |= ch == '-', ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
if(f) x = -x;
}
template <typename types, typename... Args> void read(types &x, Args&... args){
read(x), read(args...);
}
template <typename Tp> void write(Tp x){
if(x < 0) {putchar('-'); x = -x;}
Tp k = x / 10; if(k) write(k);
putchar(x - (k << 3) - (k << 1) + '0');
}
template <typename Tp> void print(Tp x, bool space = 0){
write(x);
if (space) putchar(' ');
else putchar('\n');
}
int n, q, in1, in2, in3, op, inv2, inv5;
int inp[N];
struct SB{
int A, B;
friend SB operator + (SB a, SB b){
return {(a.A + b.A) % mod, (a.B + b.B) % mod};
}
friend SB operator - (SB a, SB b){
return {(a.A - b.A + mod) % mod, (a.B - b.B) % mod};
}
friend SB operator * (SB a, SB b){
return {(a.A * b.B % mod + b.A * a.B % mod) % mod, (5 * a.A % mod * b.A % mod + a.B * b.B % mod) % mod};
}
friend bool operator == (SB a, SB b){
return (a.A == b.A) && (a.B == b.B);
}
};
int q_powint(int a, int b){
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
SB q_pow(SB a, int b){
SB res = {0, 1};
while (b) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
SB frac(SB a){
return SB{a.B * inv5 % mod, a.A};
}
struct STn{
SB sum1, sum2, tag1, tag2;
};
struct ST{
STn a[N << 2];
STn merge(STn a, STn b){
return STn{a.sum1 + b.sum1, a.sum2 + b.sum2, {0, 1}, {0, 1}};
}
void build(int p, int l, int r){
a[p].tag1.B = a[p].tag2.B = 1;
if (l == r) {
a[p].sum1 = q_pow(SB{inv2, inv2}, inp[l]);
a[p].sum2 = q_pow(SB{mod - inv2, inv2}, inp[l]);
return ;
}
build(ls, l, mid); build(rs, mid + 1, r);
a[p] = merge(a[ls], a[rs]);
}
void change_t(int p, SB k1, SB k2){
a[p].sum1 = a[p].sum1 * k1;
a[p].tag1 = a[p].tag1 * k1;
a[p].sum2 = a[p].sum2 * k2;
a[p].tag2 = a[p].tag2 * k2;
}
void push_down(int p){
if ((a[p].tag1 == SB{0, 1}) && (a[p].tag2 == SB{0, 1})) return ;
change_t(ls, a[p].tag1, a[p].tag2);
change_t(rs, a[p].tag1, a[p].tag2);
a[p].tag1 = a[p].tag2 = SB{0, 1};
}
void change(int p, int l, int r, int x, int y, SB k1, SB k2){
if (x <= l && r <= y) return change_t(p, k1, k2);
push_down(p);
if (x <= mid) change(ls, l, mid, x, y, k1, k2);
if (y > mid) change(rs, mid + 1, r, x, y, k1, k2);
a[p] = merge(a[ls], a[rs]);
}
STn ask(int p, int l, int r, int x, int y){
if (x <= l && r <= y) return a[p];
push_down(p);
if (y <= mid) return ask(ls, l, mid, x, y);
if (x > mid) return ask(rs, mid + 1, r, x, y);
return merge(ask(ls, l, mid, x, y), ask(rs, mid + 1, r, x, y));
}
}tree;
signed main(){
inv2 = q_powint(2, mod - 2);
inv5 = q_powint(5, mod - 2);
read(n, q);
for (int i = 1; i <= n; i ++) read(inp[i]);
tree.build(1, 1, n);
while (q --) {
read(op);
if (op == 1) {
read(in1, in2, in3);
tree.change(1, 1, n, in1, in2, q_pow(SB{inv2, inv2}, in3), q_pow(SB{mod - inv2, inv2}, in3));
}
if (op == 2) {
read(in1, in2);
STn res = tree.ask(1, 1, n, in1, in2);
SB res2 = frac(res.sum1 - res.sum2);
int ans = res2.B;
print(ans);
}
}
return 0;
}