SRM639Div1Medium
問題
N*Mの二次元配列が与えられる。各要素は0か1である。任意の境界を選択し、そこを基準に左右の二次配列が等しい時、サイズの小さい配列を削除することができる。
以上の操作をした際に得られる、配列の種類の総数を求めよ。
解法
縦方向に折りたたむ場合と横方向に折りたたむ場合は、それぞれ独立に計算できる。それぞれの場合はの種類の総数を求め、最後に掛け合わせることで答えが求まる。
どちらかの方向に折りたたむ場合の種類の総数の求め方を説明する。削除可能な配列を上と下から、求めていく。ある配列が削除可能かどうかは、互いの配列が等しいかを事前に計算しておくことで、で求めることができる。
計算量
