エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
m項間漸化式の第n項までの和を$O(m ^ 2 log n)$で - ブログのとさか
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
m項間漸化式の第n項までの和を$O(m ^ 2 log n)$で - ブログのとさか
この記事では項間漸化式の第項までの和をで求める方法について説明します。 @mt_caret がnth Fibonacci ... この記事では項間漸化式の第項までの和をで求める方法について説明します。 @mt_caret がnth Fibonacci number in O(logn)という記事を書いていたのを見て、以前ブログに書こうと思っていて完全に忘却していたネタを思い出したので書きました。 イントロ 項間漸化式の第項 項間の線形漸化式*1 は、次のように行列で表現し、繰り返し二乗法を使って乗を計算することでで求めることができます。 $$A= \begin{pmatrix} c_{m -1} & \cdots & c_{1} & c_{0} \\ 1 & \cdots & 0 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & 1 & 0 \end{pmatrix} $$ $$ \begin{pmatrix} a_{n+m -1} \\ a_{n+m