c++ - 再帰関係と行列べき乗を見つける

Question

Codechef でこの問題の再発関係を見つけようとしています。

見つけたら、行列の累乗を使用して簡単に解くことができます。しかし、正しい答えを得る方法を理解するのに苦労しています。ここに解決策がありますが、誰かがそれをより良い方法で説明してくれませんか?

ここに画像の説明を入力

再発またはそのようなものを見つけるための簡単な経験則はありますか? ありがとう！

score 1 · Accepted Answer

再発を見つけるための「一般的なルール」は、問題の解決策がより小さな問題の解決策にどのように関連しているかを理解することです。しかしそれ以上に、再発を見つけるための一般的な手順はないと思います。

この特定の例では、再発を見つける方法を次に示します。

サイズ N の大きな壁があるとします。ここで、壁の端を見てください。より正確には、壁の端から、「垂直方向の分離」がある最初の場所、つまり壁を L 字型にならずに 2 つの小さな壁に分割できる最初の場所を見つけます。

例：

(A) ここに壁があります:

X###X#XXX#X

XX#XX#XXXXX

最後に分割すると、次のようになります。

X###X#XXX #X

XX#XX#XXX XX

(B) もう一つの壁

X####X#XXX

XX#XX#XXX

最後に分割すると、次のようになります。

X####X# XXX

XX#XX# XXX

壁の割れ目と端の間にある小さな壁片のサイズはどれくらいですか? そうですね、1 つ、2 つ、または 3 つ持つことができますが、それ以上にすることはできません (それ以外の場合は、最小の分割を行うことができます)。

小さなピースの可能性は、実際にはあなたの質問で与えられたものです (はい、7 つの小さなブロック)。

したがって、サイズ N の壁を構築するには、次のことを行う必要があります。

したがって、サイズ N の可能な壁の数 T(N) は

そして、そこにあなたの再発があります。

それが役に立てば幸い！

1 に答える 1