Divide and conquer で組み合わせ爆発に立ち向かえ Part 2 - ita’s diary

転送行列編：http://d.hatena.ne.jp/ita/20120915/p1 の続き 「おぬしらのアイディアはこうじゃな。真ん中のところの状態をi番目の状態に固定して、それで左と右で許される経路の数を数える。それをLi, RiとおけばΣLiRiが求める答え、と」 「じゃあ更に分割して三人で手分けしたらどうなるかの。」 真ん中を二箇所で分割して状態をiとjに固定、そこでLiとRj、それに真ん中で許される経路の数Mijを数え上げる。最終的な答えはΣLiMijRj となるわのう。で、これはな、ベクトルL、行列M、ベクトルRをかけたのと同じ式じゃ。簡単にこう書こう ＜L|M|R＞。 （口調めんどうなんで以下普通） もっと分割を増やすとどうなるか。 ここで重要なのはiとjではさまれた部分と、jとkではさまれた部分は条件が全く同じということ。なので図で書いた行列Mと行列Nは同じものを使える。