アルゴリズムと数学056 - Recurrence Formula 2

アルゴリズムと数学056 - Recurrence Formula 2

解法: 行列冪乗

遷移が線形なので，行列冪により \(O(M^{3} log N)\) で求まる． ここで，\(M\)が行列の次数，\(N\) は行列冪の指数．
遷移が \[ \begin{pmatrix} a_{n} & a_{n+1} & a_{n+2} \end{pmatrix} = \begin{pmatrix} a_{n-1} & a_{n} & a_{n+1} \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix} \] となるので，初期ベクトルと冪を用いて \[ \begin{pmatrix} a_{n} & a_{n+1} & a_{n+2} \end{pmatrix} = \begin{pmatrix} a_{0} & a_{1} & a_{2} \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}^{N} \] と書ける． 行列を一つ掛けると index が一つ増えるので， \(N\)乗で index が \(N\)増える．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  n--;

  Matrix<mint> a(vector<vector<mint>>{

    {0,0,1},

    {1,0,1},

    {0,1,1}

  });

  Matrix<mint> ini(vector<vector<mint>>{

    {1,1,2}

  });

  cout << (ini*a.pow(n)).get(0,0).val() << endl;

 

  return 0;

}