SRM654Div1Easy
問題
サイズNの配列が与えられる。各要素は小文字のアルファベット(a-z)か?である。?は小文字のアルファベットに変更することができ、各アルファベットへの変換確率はpで与えられる。
全ての要素が同じ部分配列の数がその配列のスコアとする。与えられた配列のスコアの期待値を求めよ。
解法
?を含む部分配列を全列挙し、各部分配列のスコアを数え上げることで答えが求まる。毎回部分配列の分布を計算するとになる。最初と最後の要素以外の変更はないので、使い回すことができる。このことを利用すれば
に削減できる。
計算量
は指数計算
