ACM学习历程—Codeforces 446C DZY Loves Fibonacci Numbers(线段树 && 数论)
Description
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
F1 = 1; F2 = 1; Fn = Fn - 1 + Fn - 2 (n > 2).
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: a1, a2, ..., an. Moreover, there are m queries, each query has one of the two types:
- Format of the query "1 lr". In reply to the query, you need to add Fi - l + 1 to each element ai, where l ≤ i ≤ r.
- Format of the query "2 lr". In reply to the query you should output the value of modulo 1000000009 (109 + 9).
Help DZY reply to all the queries.
Input
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — initial array a.
Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1 ≤ l ≤ r ≤ n holds.
Output
For each query of the second type, print the value of the sum on a single line.
Sample Input
Input
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
Output
17
12
Sample Output
Test case #1Total explored area: 180.00
Hint
After the first query, a = [2, 3, 5, 7].
For the second query, sum = 2 + 3 + 5 + 7 = 17.
After the third query, a = [2, 4, 6, 9].
For the fourth query, sum = 2 + 4 + 6 = 12.
这个题目是段更新的线段树，但是题目段内增加的不是固定值，是Fibonacci数列，而且每个点也不是增加的固定的某个Fibonacci值，增加的是Fi - l + 1。
目前有两种处理方式。
方式一：（等效替代）
对于Fn = Fn - 1 + Fn - 2，根据特征方程可以得到解是
Fn = (1/sqrt(5)*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)
但是式子里面带有sqrt(5)，double型精度丢失严重，于是这里需要一个小技巧。
对于sqrt(5),由于式子展开后不包含sqrt(5)，而且sqrt(5)唯一的特征就是平方后等于5，这样就可以找一个替代的数，在模10^9+9的情况下，平方等于5就可以。这样这个数在模10^9+9的情况下，运算结果是和sqrt(5)一致的。
然后弄个程序找一下是383008016和616991993，随便一个就行。
然后就是1/sqrt(5)这个也需要在模运算下处理，这个式子的含义就是sqrt(5)的逆元，这样就弄个程序找一下逆元就可以了。
然后式子就转换成Fn = K*(X^n-Y^n)了。
就是两个等比数列了。
然后对于和s = sumFrom(1,n)(K*X^i)
可以拆分成 s = sumFrom(1,n)(K*X^i) = sumFrom(1, t)(K*X^i) + sumFrom(t+1, n)(K*X^i)
= sumFrom(1, t)(K*X^i) + X^t*sumFrom(1, n-t)(K*X^i)
这样区间段更新的时候，对每一个等比数列就满足区间的拆分了。
这样就只需要维护前面的系数k了：
刚进去时，X的系数是K，Y的系数是-K
第一次区间拆分后前一段区间是K，后一段就是X^t*K了。
这个t就是由前一段更新区间长度得到的。（这里需要注意的是，我代码里面用x和y数组已经预先处理的两个等比数列的前n项和，但是程序里在区间拆分时会出现下标访问-1的情况，这里需要特判一下。）
最后区间段更新就是求一个等比数列的前n项和，这里我预先进行了处理。
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <algorithm> #define LL long long using namespace std; //fn = (1/sqrt(5)*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n) const LL MOD = 1e9+9; const LL UNIT = 383008016;//sqrt(5)在模MOD的情况下的等价数，616991993也是 const LL X = ((1+UNIT+MOD)/2)%MOD;//特征根，加MOD为了化为偶数 const LL Y = (1-UNIT+MOD)/2;//特征根 const LL K = 276601605;//1/sqrt(5) //线段树 //区间每点增值，求区间和 const int maxN = 300005; LL x[maxN], y[maxN]; int n, m, a[maxN]; struct node { int lt, rt; LL val, mul1, mul2;//mul是区间乘的值,val是区间和 }tree[4*maxN]; //向下更新 void pushDown(int id) { LL tmp; if (tree[id].mul1 != 0) { tree[id<<1].mul1 += tree[id].mul1; tree[id<<1].mul1 %= MOD; tree[id<<1].val += x[tree[id<<1].rt-tree[id<<1].lt+1]*tree[id].mul1%MOD; tree[id<<1].val %= MOD; tmp = x[tree[id<<1].rt-tree[id<<1].lt+1]-x[tree[id<<1].rt-tree[id<<1].lt]; tmp = (tmp%MOD+MOD)%MOD; tmp = tree[id].mul1*tmp%MOD; tree[id<<1|1].mul1 += tmp; tree[id<<1|1].mul1 %= MOD; tree[id<<1|1].val += x[tree[id<<1|1].rt-tree[id<<1|1].lt+1]*tmp%MOD; tree[id<<1|1].val %= MOD; tree[id].mul1 = 0; } if (tree[id].mul2 != 0) { tree[id<<1].mul2 += tree[id].mul2; tree[id<<1].mul2 %= MOD; tree[id<<1].val += y[tree[id<<1].rt-tree[id<<1].lt+1]*tree[id].mul2%MOD; tree[id<<1].val %= MOD; tmp = y[tree[id<<1].rt-tree[id<<1].lt+1]-y[tree[id<<1].rt-tree[id<<1].lt]; tmp = (tmp%MOD+MOD)%MOD; tmp = tree[id].mul2*tmp%MOD; tree[id<<1|1].mul2 += tmp; tree[id<<1|1].mul2 %= MOD; tree[id<<1|1].val += y[tree[id<<1|1].rt-tree[id<<1|1].lt+1]*tmp%MOD; tree[id<<1|1].val %= MOD; tree[id].mul2 = 0; } } //向上更新 void pushUp(int id) { tree[id].val = tree[id<<1].val + tree[id<<1|1].val; tree[id].val %= MOD; } //建立线段树 void build(int lt, int rt, int id) { tree[id].lt = lt; tree[id].rt = rt; tree[id].val = 0;//每段的初值，根据题目要求 tree[id].mul1 = tree[id].mul2 = 0; if (lt == rt) { tree[id].val = a[lt]; return; } int mid = (lt + rt) >> 1; build(lt, mid, id<<1); build(mid + 1, rt, id<<1|1); pushUp(id); } void add(int lt, int rt, int id, LL pls1, LL pls2) { pls1 = (pls1%MOD+MOD)%MOD; pls2 = (pls2%MOD+MOD)%MOD; if (lt <= tree[id].lt && rt >= tree[id].rt) { tree[id].mul1 += pls1; tree[id].mul1 %= MOD; tree[id].mul2 += pls2; tree[id].mul2 %= MOD; tree[id].val += pls1*x[tree[id].rt-tree[id].lt+1]%MOD; tree[id].val += pls2*y[tree[id].rt-tree[id].lt+1]%MOD; tree[id].val %= MOD; return; } pushDown(id); int mid = (tree[id].lt + tree[id].rt) >> 1; if (lt <= mid) add(lt, rt, id<<1, pls1, pls2); if (rt > mid) if (mid >= max(tree[id<<1].lt,lt)) add(lt, rt, id<<1|1, pls1*(x[mid-max(tree[id<<1].lt,lt)+1]-x[mid-max(tree[id<<1].lt,lt)]), pls2*(y[mid-max(tree[id<<1].lt,lt)+1]-y[mid-max(tree[id<<1].lt,lt)])); else add(lt, rt, id<<1|1, pls1, pls2); pushUp(id); } //查询某段区间内的和 int query(int lt, int rt, int id) { if (lt <= tree[id].lt && rt >= tree[id].rt) return tree[id].val; pushDown(id); int mid = (tree[id].lt + tree[id].rt) >> 1; int ans = 0; if (lt <= mid) ans += query(lt, rt, id<<1); if (rt > mid) ans += query(lt, rt, id<<1|1); return ans%MOD; } void init() { x[0] = y[0] = 0; x[1] = X; y[1] = Y; for (int i = 2; i < maxN; ++i) { x[i] = (X*x[i-1]+X)%MOD; y[i] = (Y*y[i-1]+Y)%MOD; } } void input() { for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); build(1, n, 1); } void work() { int op, from, to; LL ans; for (int i = 0; i < m; ++i) { scanf("%d%d%d", &op, &from, &to); if (op == 1) add(from, to, 1, K, -K); else { ans = query(from, to, 1); printf("%I64d ", ans); } } } int main() { //freopen("test.in", "r", stdin); init(); while (scanf("%d%d", &n, &m) != EOF) { input(); work(); } return 0; }
方式二：（Fibonacci性质）
假设某两项a, b，那么后面的项必然是a+b, a+2b, 2a+3b......
a的系数序列为k[i] = 1, 0, 1, 1, 2.....从第0项开始，
b的系数从第一项开始。
对于f[i], f[i+1]后面某一项，f[p]
那么f[p] = k[p-i]f[i] + k[p-i+1]f[i+1]
此外，
sumFrom(lt, rt)f[p]
= sumFrom(lt, rt)(k[p-lt]f[lt]+k[p-lt+1]f[lt+1])
= f[lt]sumFrom(lr, rt)k[p-lt] + f[lt+1]sumFrom(lt, rt)k[p-lt+1]
= f[lt]s[rt-lt] + f[lt+1](s[rt-lt+1]-s[0])
此外还有一个前提是两个Fibonacci数列的和依旧是Fibonacci。
然后维护系数f[lt]和f[lt+1]就可以了。
不过依旧需要注意的是当更新区间完全在右子树时需要特殊判断u1和u2是直接传入右子树还是需要位移后传入。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <set> 7 #include <map> 8 #include <queue> 9 #include <string> 10 #include <algorithm> 11 #define LL long long 12 13 using namespace std; 14 15 //线段树 16 //区间每点增值，求区间和 17 const LL MOD = 1e9+9; 18 const int maxN = 300005; 19 int a[maxN], n, m; 20 LL k[maxN], s[maxN]; 21 struct node 22 { 23 int lt, rt; 24 LL val, u1, u2;//u1,u2表示以这两个起始的Fibonacci数列 25 }tree[4*maxN]; 26 27 //向下更新 28 void pushDown(int id) 29 { 30 LL tmp, u1, u2; 31 if (tree[id].u1 != 0 || tree[id].u2 != 0) 32 { 33 tree[id<<1].u1 += tree[id].u1; 34 tree[id<<1].u2 += tree[id].u2; 35 tree[id<<1].u1 %= MOD; 36 tree[id<<1].u2 %= MOD; 37 tmp = tree[id].u1*s[tree[id<<1].rt-tree[id<<1].lt]%MOD; 38 tmp += tree[id].u2*(s[tree[id<<1].rt-tree[id<<1].lt+1]-s[0])%MOD; 39 tmp %= MOD; 40 tree[id<<1].val += tmp; 41 tree[id<<1].val %= MOD; 42 43 u1 = k[tree[id<<1|1].lt-tree[id<<1].lt]*tree[id].u1%MOD; 44 u1 += k[tree[id<<1|1].lt-tree[id<<1].lt+1]*tree[id].u2%MOD; 45 u1 %= MOD; 46 u2 = k[tree[id<<1|1].lt-tree[id<<1].lt+1]*tree[id].u1%MOD; 47 u2 += k[tree[id<<1|1].lt-tree[id<<1].lt+2]*tree[id].u2%MOD; 48 u2 %= MOD; 49 tree[id<<1|1].u1 += u1; 50 tree[id<<1|1].u2 += u2; 51 tree[id<<1|1].u1 %= MOD; 52 tree[id<<1|1].u2 %= MOD; 53 tmp = u1*s[tree[id<<1|1].rt-tree[id<<1|1].lt]%MOD; 54 tmp += u2*(s[tree[id<<1|1].rt-tree[id<<1|1].lt+1]-s[0])%MOD; 55 tmp %= MOD; 56 tree[id<<1|1].val += tmp; 57 tree[id<<1|1].val %= MOD; 58 tree[id].u1 = 0; 59 tree[id].u2 = 0; 60 } 61 } 62 63 //向上更新 64 void pushUp(int id) 65 { 66 tree[id].val = (tree[id<<1].val + tree[id<<1|1].val)%MOD; 67 } 68 69 //建立线段树 70 void build(int lt, int rt, int id) 71 { 72 tree[id].lt = lt; 73 tree[id].rt = rt; 74 tree[id].val = 0;//每段的初值，根据题目要求 75 tree[id].u1 = tree[id].u2 = 0; 76 if (lt == rt) 77 { 78 tree[id].val = a[lt]; 79 return; 80 } 81 int mid = (lt + rt) >> 1; 82 build(lt, mid, id<<1); 83 build(mid+1, rt, id<<1|1); 84 pushUp(id); 85 } 86 87 void add(int lt, int rt, int id, int u1, int u2) 88 { 89 u1 %= MOD; 90 u2 %= MOD; 91 if (lt <= tree[id].lt && rt >= tree[id].rt) 92 { 93 LL tmp; 94 tree[id].u1 += u1; 95 tree[id].u2 += u2; 96 tmp = u1*s[tree[id].rt-tree[id].lt]%MOD; 97 tmp += u2*(s[tree[id].rt-tree[id].lt+1]-s[0])%MOD; 98 tmp %= MOD; 99 tree[id].val += tmp; 100 tree[id].val %= MOD; 101 return; 102 } 103 pushDown(id); 104 int mid = (tree[id].lt + tree[id].rt) >> 1; 105 if (lt <= mid) 106 add(lt, rt, id<<1, u1, u2); 107 if (rt > mid) 108 if (mid-max(lt, tree[id].lt) >= 0) 109 add(lt, rt, id<<1|1, 110 k[mid+1-max(lt, tree[id].lt)]*u1%MOD+k[mid+2-max(lt, tree[id].lt)]*u2%MOD, 111 k[mid+2-max(lt, tree[id].lt)]*u1%MOD+k[mid+3-max(lt, tree[id].lt)]*u2%MOD); 112 else 113 add(lt, rt, id<<1|1, u1, u2); 114 pushUp(id); 115 } 116 117 //查询某段区间内的和 118 int query(int lt, int rt, int id) 119 { 120 if (lt <= tree[id].lt && rt >= tree[id].rt) 121 return tree[id].val; 122 pushDown(id); 123 int mid = (tree[id].lt + tree[id].rt) >> 1; 124 int ans = 0; 125 if (lt <= mid) 126 ans += query(lt, rt, id<<1); 127 if (rt > mid) 128 ans += query(lt, rt, id<<1|1); 129 return ans%MOD; 130 } 131 132 void init() 133 { 134 k[0] = 1; 135 k[1] = 0; 136 s[0] = s[1] = 1; 137 for (int i = 2; i < maxN; ++i) 138 { 139 k[i] = (k[i-1]+k[i-2])%MOD; 140 s[i] = (s[i-1]+k[i])%MOD; 141 } 142 } 143 144 void input() 145 { 146 for (int i = 1; i <= n; ++i) 147 scanf("%d", &a[i]); 148 build(1, n, 1); 149 } 150 151 void work() 152 { 153 int op, from, to; 154 LL ans; 155 for (int i = 0; i < m; ++i) 156 { 157 scanf("%d%d%d", &op, &from, &to); 158 if (op == 1) 159 add(from, to, 1, 1, 1); 160 else 161 { 162 ans = query(from, to, 1); 163 printf("%I64d ", ans); 164 } 165 } 166 } 167 168 int main() 169 { 170 //freopen("test.in", "r", stdin); 171 init(); 172 while (scanf("%d%d", &n, &m) != EOF) 173 { 174 input(); 175 work(); 176 } 177 return 0; 178 }