サーチ…
例題の問題を解くための行列のべき乗
f（n）を見つける：n 番目のフィボナッチ数。 nが比較的小さいときに問題は非常に簡単です。 f(n) = f(n-1) + f(n-2)簡単な再帰を使うことができます。あるいは、同じ関数を繰り返し計算することを避けるために動的計画法を使うこともできます。しかし、 0 <n <109の場合、f（n）mod 999983を見つけると、問題があるとすればどうなるでしょうか？動的プログラミングは失敗するので、どのようにこの問題に取り組んでいますか？
最初に、行列累乗が再帰的関係を表すのに役立つ方法を見てみましょう。
前提条件：
- 2つの行列を考えると、その製品を見つける方法を知っている。さらに、2つの行列の積行列とそれらのうちの1つが、他の行列を見つける方法を知っていると仮定すると、
- 径d X dのマトリックスを与え、（D 3ログ（n））はOで乗そのNを検索する方法を知っています。
パターン：
最初は再帰的関係が必要であり、既に知られている状態集合から所望の状態に導くことができる行列Mを求めたい。与えられた反復関係のk個の状態を知っており、 （k + 1） 番目の状態を見つけたいとします。 Mを k×k行列とし、漸化関係の既知の状態から行列A：[k X 1]を構築すると、ここで行列Bを得ることができます。[k X 1]次の状態、すなわちMXA = Bとなる。
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
M X | f(n-2) | = | f(n-1) |
| ...... | | ...... |
| f(n-k) | |f(n-k+1)|
Mを適切に設計できれば、私たちの仕事は完了します！行列は、漸化関係を表すために使用されます。
タイプ1：
f(n) = f(n-1) + f(n-2)
f(n+1) = f(n) + f(n-1) 。
f(n)とf(n-1)を知っているとしましょう。私たちはf(n+1)を見つけたいと思っています。
上記のような状況から、以下に示すように、行列Aと行列Bを形成することができる。
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
[注：行列Aは、 f(n+1)依存するすべての状態が存在するように常に設計されます]
ここで、上記のようにMXA = Bを満たすような2X2行列Mを設計する必要があります。
Bの最初の要素であるf(n+1)実際にはf(n) + f(n-1) 。これを得るには、行列Aから、 1 X f（n）と1 X f（n-1）が必要です。 Mの最初の行は[1 1]になります。
| 1 1 | X | f(n) | = | f(n+1) |
| ----- | | f(n-1) | | ------ |
[注：-----は、この値に心配していないことを意味します。]
同様に、Bの2番目の項目であるf(n)単にAから1×F（n）をとることによって得できるので、Mの2行は[1 0]です。
| ----- | X | f(n) | = | ------ |
| 1 0 | | f(n-1) | | f(n) |
次に、希望の2×2行列Mを得る。
| 1 1 | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
これらの行列は単純に行列乗算を使用して導出されます。
タイプ2：
ここで 、 aとbは定数ですf(n) = a X f(n-1) + b X f(n-2)探してみましょう。
これは、 f(n+1) = a X f(n) + b X f(n-1) 。
これまでのところ、行列の次元は依存関係の数に等しくなることは明らかである。すなわち、この例では2である。したがって、 AとBに対して、サイズ2 X 1の2つの行列を作ることができる。
Matrix A Matrix B
| f(n) | | f(n+1) |
| f(n-1) | | f(n) |
ここで、 f(n+1) = a X f(n) + b X f(n-1)場合、目的行列Mの第1行に[a、b]が必要である。そして、 Bの2番目の項目、すなわちf(n)については既に行列Aにあるので、行列Mの2番目の行を[1 0]に導くだけです。今回は次のようになります：
| a b | X | f(n) | = | f(n+1) |
| 1 0 | | f(n-1) | | f(n) |
かなりシンプルな、ええ？
タイプ3：
この段階まで生き残っていれば、はるかに成長してきましたが、今度は少し複雑な関係に直面しましょう： f(n) = a X f(n-1) + c X f(n-3)
おっと！数分前、私たちが見たのは連続した状態でしたが、ここでは状態f（n-2）はありません。今？
実際、この問題は次のように我々は関係を変換することができ、もうありません： f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3)演繹f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2)さて、これは実際にはタイプ2で説明されている形式であることがわかります。ここでは、目的行列Mは3 X 3になり、要素は次のようになります。
| a 0 c | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 1 0 | | f(n-2) | | f(n-1) |
これらは、タイプ2と同じ方法で計算されます。難しい場合は、ペンとペーパーで試してみてください。
タイプ4：
人生は地獄のように複雑になっている、と氏は、問題は今見つけることが求められますf(n) = f(n-1) + f(n-2) + c 、cは任意の定数です。
今これは新しいものであり、過去には、乗算の後、 Aの各状態がBの次の状態に変換されたことがわかりました 。
f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on
したがって、通常は以前の方法では取得できませんが、 cを状態として追加する方法はありますか？
| f(n) | | f(n+1) |
M X | f(n-1) | = | f(n) |
| c | | c |
さて、 Mをデザインするのはそれほど難しくありません。これはどのように行われますが、確認することを忘れないでください：
| 1 1 1 | | f(n) | | f(n+1) |
| 1 0 0 | X | f(n-1) | = | f(n) |
| 0 0 1 | | c | | c |
タイプ5：
f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e見つける。あなたのための運動としてそれを残しましょう。まず、状態と行列Mを見つけようとします。それがあなたの解決策と合っているかどうかを確認してください。行列AとBも見いだす。
| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |
タイプ6：
ときどき再発は次のように与えられます：
f(n) = f(n-1) -> if n is odd
f(n) = f(n-2) -> if n is even
要するに：
f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)
ここでは、奇数偶数に基づいて関数を分割し、両方の2つの行列を保持し、それらを別々に計算することができます。
タイプ7：
少し自信がありませんか？よかったね。時には、関心のある場所で複数の再発を維持する必要がある場合もあります。たとえば、再発させるには、次のようにします。
g(n) = 2g(n-1) + 2g(n-2) + f(n)
ここで、再帰g（n）はf(n)依存し、これは同じ行列であるが増加した次元で計算することができる。これらから、まず行列AとBを設計します。
Matrix A Matrix B
| g(n) | | g(n+1) |
| g(n-1) | | g(n) |
| f(n+1) | | f(n+2) |
| f(n) | | f(n+1) |
ここで、 g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n)ここで、上記のプロセスを使用して、目的行列Mを以下のように求めることができます。
| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |
したがって、これらは単純な手法で解決するために使用される漸化関係の基本的なカテゴリです。
