FZOJ P2109 【卡德加的兔子】

题目描述

卡德加喜欢养兔子。他在达拉然的下水道里放了 $N$ 个兔笼（编号从 $1$ 到 $N$），里面养着他从德拉诺带来的兔子。它们的繁殖遵循斐波那契数列的规律：刚开始时，笼子里有一对刚出生的兔子。每对兔子在出生第二个月后，每个月都生一对兔子。（第一个月结束后有 $1$ 对兔子。第二个月结束后有 $2$ 对。）

卡德加从苏拉玛的的大魔导师艾利桑德那边学习了先进的扭曲时空法术。有时候，他会对一排连续的兔笼（从第 $L$ 号到第 $R$ 号）释放时光流逝法术，让这些兔笼里的时间前进 $K$ 个月。另外一些时候，他想喂一下兔子，所以他想知道第 $L$ 号到第 $R$ 号兔笼里有多少只兔子。

（假设这些操作都是在一个月以内完成的，不需要考虑自然时间对兔子的影响。)

输入

第一行两个整数 $N,M$, 表示兔笼的数量和操作的数量。

接下来 $M$ 行，每行包含三个数 $L,R,K$。如果 $K > 0$，说明卡德加在使用时光流逝，编号 $L$ 到 $R$ 的兔笼时间前进 $K$ 个月。如果 $K = 0$，说明他只是想喂兔子了，输出这些兔笼里有多少兔子。

输出

对每个喂兔子的操作，输出兔子的数量。答案模 $10007$。

样例输入
10 10
1 3 2
1 1 0
2 4 0
3 5 0
4 7 3
3 5 0
1 4 0
2 7 0
1 9 4
2 10 0
样例输出
2
5
4
8
9
16
121
来源

2017 年 NOIP 夏令营

看到了询问区间，马上想到线段树；看到了斐波那契数列，马上想到矩阵快速幂。问题在于怎么结合了。

对于两个数列，如果这两个数列都具有斐波那契性质，则这两个数列的和也具有斐波那契性质。

什么意思呢？就是说对于两个数列 $\{x_1,x_2,x_3,x_4,\dots\}$，$\{y_1,y_2,y_3,y_4,\dots\}$，如果 $x_1+x_2=x_3, x_2+x_3=x_4, \dots, y_1+y_2=y_3, y_2+y_3=y_4, \dots$

如果有一个数列 $\{z_1,z_2,z_3,z_4,\dots\}$，其中 $z_1=x_1+y_1, z_2=x_2+y_2, \dots, z_k=x_k+y_k, \dots$

则有 $z_1+z_2=z_3, z_2+z_3=z_4, \dots$

这个不难证明，利用等式的性质就好了。

利用这个特性，我们可以在线段树的每个地方存储运算时的矩阵（因为满足分配率）。更新的时候，用矩阵加法就可以了。

另外，由 $\text{BSGS}$ 算法可知，此题还有一个优化：

斐波那契数列对 $10007$ 取模时，第 $1$ 个数与第 $20017$ 个数是一样的，第 $2$ 个数与第 $20018$ 个数是一样的。

这样就可以预先算好 $20017$ 个矩阵的值了，不需要使用快速幂。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 struct Matrix {
  7   int mat[2][2];
  8   Matrix() { memset(mat, 0, sizeof mat); }
  9 };
 10 
 11 const int MaxN = 100000 + 5;
 12 const int Mod = 10007;
 13 
 14 int N, M;
 15 Matrix One, Fibo, Zero;
 16 int L[MaxN * 4], R[MaxN * 4];
 17 Matrix Sum[MaxN * 4], Tag[MaxN * 4];
 18 
 19 inline Matrix operator + (Matrix A, Matrix B) {
 20   Matrix C;
 21   for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j)
 22     C.mat[i][j] = (A.mat[i][j] + B.mat[i][j]) % Mod;
 23   return C;
 24 }
 25 
 26 inline Matrix operator * (Matrix A, Matrix B) {
 27   Matrix C;
 28   for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
 29     for (int k = 0; k < 2; ++k) C.mat[i][j] += A.mat[i][k] * B.mat[k][j] % Mod;
 30     C.mat[i][j] %= Mod;
 31   }
 32   return C;
 33 }
 34 
 35 inline Matrix operator ^ (Matrix low, int high) {
 36   Matrix ans;
 37   ans.mat[0][0] = ans.mat[1][1] = 1;
 38   while (high) {
 39     if (high & 1) ans = ans * low;
 40     high >>= 1;
 41     low = low * low;
 42   }
 43   return ans;
 44 }
 45 
 46 inline int read() {
 47   int x = 0; char c;
 48   do c = getchar(); while (c < '0' || c > '9');
 49   do x = (x << 1) + (x << 3) + c - '0', c = getchar(); while (c >= '0' && c <= '9');
 50   return x;
 51 }
 52 
 53 inline void Push_up(int i) { Sum[i] = Sum[i << 1] + Sum[i << 1 | 1]; }
 54 
 55 inline void Push_down(int i) {
 56   int lson = i << 1, rson = i << 1 | 1;
 57 
 58   Tag[lson] = Tag[lson] * Tag[i];
 59   Sum[lson] = Sum[lson] * Tag[i];
 60   Tag[rson] = Tag[rson] * Tag[i];
 61   Sum[rson] = Sum[rson] * Tag[i];
 62   Tag[i] = One;
 63 }
 64 
 65 void Build_Tree(int l, int r, int i) {
 66   L[i] = l, R[i] = r;
 67   Tag[i] = One;
 68   if (l == r) {
 69     Sum[i].mat[0][0] = Sum[i].mat[0][1] = 1;
 70     return;
 71   }
 72   int mid = L[i] + R[i] >> 1;
 73   Build_Tree(l, mid, i << 1);
 74   Build_Tree(mid + 1, r, i << 1 | 1);
 75   Push_up(i);
 76 }
 77 
 78 void Update_Tree(int l, int r, int k, int i) {
 79   if (L[i] == l && R[i] == r) {
 80     Sum[i] = Sum[i] * (Fibo ^ k);
 81     Tag[i] = Tag[i] * (Fibo ^ k);
 82     return;
 83   }
 84   Push_down(i);
 85 
 86   int mid = L[i] + R[i] >> 1;
 87   if (r <= mid) Update_Tree(l, r, k, i << 1);
 88   else if (l > mid) Update_Tree(l, r, k, i << 1 | 1);
 89   else {
 90     Update_Tree(l, mid, k, i << 1);
 91     Update_Tree(mid + 1, r, k, i << 1 | 1);
 92   }
 93   Push_up(i);
 94 }
 95 
 96 Matrix Query_Tree(int l, int r, int i) {
 97   if (L[i] == l && R[i] == r)
 98     return Sum[i];
 99   Push_down(i);
100 
101   int mid = L[i] + R[i] >> 1;
102   if (r <= mid) return Query_Tree(l, r, i << 1);
103   else if (l > mid) return Query_Tree(l, r, i << 1 | 1);
104   else {
105     Matrix lc = Query_Tree(l, mid, i << 1), rc = Query_Tree(mid + 1, r, i << 1 | 1);
106     return lc + rc;
107   }
108 }
109 
110 int main() {
111   N = read(); M = read();
112   One.mat[0][0] = One.mat[1][1] = 1;
113   Fibo.mat[0][1] = Fibo.mat[1][0] = Fibo.mat[1][1] = 1;
114   Build_Tree(1, N, 1);
115 
116   Matrix res;
117   for (int m = 1; m <= M; ++m) {
118     int l, r, k;
119     l = read(); r = read(); k = read();
120     if (k == 0) {
121       res = Query_Tree(l, r, 1);
122       printf("%d\n", res.mat[0][0]);
123     } else
124       Update_Tree(l, r, k, 1);
125   }
126 
127   return 0;
128 }

View Code