SRM650Div1Easy
問題
サイズNの文字列を考える。この文字列はAとBのみで構築されている。M個のポジションとその文字が与えられ、隣り合う文字が同じとなる箇所の個数が最小となるパターンの総数を求めよ。
解法
与えれた文字とその間の文字数で答えが求まる。
以下のような例を考える。
A**B
この場合は、
ABAB
と一意に決まる。
一方、
A**Aの場合は、
ABAA
ABAA
ABBA
の3つになる。
A****Aの場合は、
AB**BA
ABABAA
AABABA
となる。
このように、再帰でパターン数が求められる。
より注目していくと、常に*の数+1となる。
すべての間隔に対して上のパターンを求め、かけることで答えが求まる。
計算量
