1303.斐波那契前 n 项和

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。

现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Snmodm。

输入格式
共一行，包含两个整数 n 和 m。

输出格式
输出前 n 项和 Snmodm 的值。

数据范围
1≤n≤2000000000,
1≤m≤1000000010
输入样例：
5 1000
输出样例：
12
image.png

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. typedef long long LL;
  10. const int N = 3;
  12. int n, m;
  14. void mul(int c[], int a[], int b[][N])
  15. {
  16.     int temp[N] = {0};
  17.     for (int i = 0; i < N; i ++ )
  18.         for (int j = 0; j < N; j ++ )
  19.             temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
  21.     memcpy(c, temp, sizeof temp);
  22. }
  24. void mul(int c[][N], int a[][N], int b[][N])
  25. {
  26.     int temp[N][N] = {0};
  27.     for (int i = 0; i < N; i ++ )
  28.         for (int j = 0; j < N; j ++ )
  29.             for (int k = 0; k < N; k ++ )
  30.                 temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
  32.     memcpy(c, temp, sizeof temp);
  33. }
  35. int main()
  36. {
  37.     cin >> n >> m;
  39.     int f1[N] = {1, 1, 1};
  40.     int a[N][N] = {
  41.         {0, 1, 0},
  42.         {1, 1, 1},
  43.         {0, 0, 1}
  44.     };
  46.     n -- ;
  47.     while (n)
  48.     {
  49.         if (n & 1) mul(f1, f1, a);  // res = res * a
  50.         mul(a, a, a);  // a = a * a
  51.         n >>= 1;
  52.     }
  54.     cout << f1[2] << endl;
  56.     return 0;
  57. }
  59. 作者：yxc
  60. 链接：https://www.acwing.com/activity/content/code/content/210521/
  61. 来源：AcWing
  62. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

求解斐波那契数列的若干方法

链接：https://www.acwing.com/blog/content/25/