WIKI

矩阵

Fibonacci 第 n 项

大家都知道 Fibonacci 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,\dots,f_n=f_{n-1}+f_{n-2}$

现在问题很简单，输入 n 和 m，求$f_n\bmod m$

对于 100\% 的数据，$1\le n \le 2\times 10^9, 1\le m \le 10^9+10$。

$$ \begin{align} f_{n-1}+f_{n-2}=f_n\\ \end{align} $$

$$ \begin{equation} \begin{cases} f_{n-1}&+f_{n-2}&+0&=f_n \\ f_{n-1}&+0&+0&=f_{n-1}\\ 0&+f_{n-2}&+0&=f_{n-2} \end{cases} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} f_{n-1} \\ f_{n-2} \\ f_{n-3} \end{pmatrix}=\begin{pmatrix} f_n \\ f_{n-1} \\ f_{n-2} \end{pmatrix} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} f_{3} \\ f_{2} \\ f_{1} \end{pmatrix}=\begin{pmatrix} f_4 \\ f_{3} \\ f_{2} \end{pmatrix} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^2\begin{pmatrix} f_{3} \\ f_{2} \\ f_{1} \end{pmatrix}=\begin{pmatrix} f_5 \\ f_{4} \\ f_{3} \end{pmatrix} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^n\begin{pmatrix} f_{3} \\ f_{2} \\ f_{1} \end{pmatrix}=\begin{pmatrix} f_{n+3} \\ f_{n+2} \\ f_{n+1} \end{pmatrix} \end{equation} $$

code

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
struct matrix {
  int n, m;
  vector<vector<int>> a;
  matrix(int n, int m) {
    this->n = n;
    this->m = m;
    a.resize(n, vector<int>(m));
  }
};
matrix mul(const matrix &a, const matrix &b, int n, int m, int k, int q) {
  matrix c(n, k);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int t = 0; t < k; t++) {
        c.a[i][t] += a.a[i][j] * b.a[j][t];
        c.a[i][t] %= q;
      }
    }
  }
  return c;
}
matrix qmi(matrix a, int b, int q, int n) {
  matrix res(n, n);
  for (int i = 0; i < n; i++) res.a[i][i] = 1;
  while (b) {
    if (b & 1) {
      res = mul(res, a, n, n, n, q);
    }
    b >>= 1;
    a = mul(a, a, n, n, n, q);
  }
  return res;
}
int f[5];
void solve() {
  f[1] = 1, f[2] = 1, f[3] = 2, f[4] = 3;
  cin >> n >> m;
  matrix e(3, 3);
  e.a[0][0] = e.a[0][1] = e.a[1][0] = e.a[2][1] = 1;
  matrix a(3, 1);
  a.a[0][0] = f[3], a.a[1][0] = f[2], a.a[2][0] = f[1];
  if (n <= 3) {
    cout << f[n] << "\n";
  } else {
    n -= 3;
    matrix ee = qmi(e, n, m, 3);
    matrix ans = mul(ee, a, 3, 3, 1, m);
    cout << ans.a[0][0] << "\n";
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}

Fibonacci 前 n 项和

大家都知道 Fibonacci 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n-1}+f_{n-2}$。

现在问题很简单，输入 n 和 m，求 ${f_n}$ 的前 n 项和 $S_n\bmod m$。

$ 1\le n \le 2\times 10^9, 1\le m \le 10^9+10$
$$ \begin{align} f_{n-1}+f_{n-2}=f_n\\ \end{align} $$

$$ \begin{equation} \begin{cases} S_{n-1}&+0&+f_n&=S_n \\ S_{n-1}&+0&+0&=S_{n-1}\\ 0&+S_{n-2}&+0&=S_{n-2} \end{cases} \end{equation} $$

$$ \begin{align} f_n=f_{n-1}+f_{n-2}&=S_{n-1}-S_{n-2}+S_{n-2}-S_{n-3}\\ f_n&=S_{n-1}-S_{n-3} \end{align} $$

$$ \begin{equation} \begin{cases} 2S_{n-1}&+0&-S_{n-3}&=S_n \\ S_{n-1}&+0&+0&=S_{n-1}\\ 0&+S_{n-2}&+0&=S_{n-2} \end{cases} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 2 & 0 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} S_{n-1} \\ S_{n-2} \\ S_{n-3} \end{pmatrix}=\begin{pmatrix} S_n \\ S_{n-1} \\ S_{n-2} \end{pmatrix} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 2 & 0 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} S_{3} \\ S_{2} \\ S_{1} \end{pmatrix}=\begin{pmatrix} S_4 \\ S_{3} \\ S_{2} \end{pmatrix} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 2 & 0 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^2\begin{pmatrix} S_{3} \\ S_{2} \\ S_{1} \end{pmatrix}=\begin{pmatrix} S_5 \\ S_{4} \\ S_{3} \end{pmatrix} \end{equation} $$

$$ \begin{equation} \begin{pmatrix} 2 & 0 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^n\begin{pmatrix} S_{3} \\S_{2} \\ S_{1} \end{pmatrix}=\begin{pmatrix} S_{n+3} \\ S_{n+2} \\ S_{n+1} \end{pmatrix} \end{equation} $$

code

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
struct matrix {
  int n, m;
  vector<vector<int>> a;
  matrix(int n, int m) {
    this->n = n;
    this->m = m;
    a.resize(n, vector<int>(m));
  }
};
matrix mul(const matrix &a, const matrix &b, int n, int m, int k, int q) {
  matrix c(n, k);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int t = 0; t < k; t++) {
        c.a[i][t] += a.a[i][j] * b.a[j][t];
        c.a[i][t] += q;
        c.a[i][t] %= q;
      }
    }
  }
  return c;
}
matrix qmi(matrix a, int b, int q, int n) {
  matrix res(n, n);
  for (int i = 0; i < n; i++) res.a[i][i] = 1;
  while (b) {
    if (b & 1) {
      res = mul(res, a, n, n, n, q);
    }
    b >>= 1;
    a = mul(a, a, n, n, n, q);
  }
  return res;
}
int S[5];
void solve() {
  S[1] = 1, S[2] = 2, S[3] = 4, S[4] = 7;
  cin >> n >> m;
  matrix e(3, 3);
  e.a[0][0] = 2;
  e.a[0][2] = -1;
  e.a[1][0] = e.a[2][1] = 1;
  matrix a(3, 1);
  a.a[0][0] = S[3], a.a[1][0] = S[2], a.a[2][0] = S[1];
  if (n <= 3) {
    cout << S[n] << "\n";
  } else {
    n -= 3;
    matrix ee = qmi(e, n, m, 3);
    matrix ans = mul(ee, a, 3, 3, 1, m);
    cout << ans.a[0][0] << "\n";
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}