きままにものづくり

日々の気付いたことなんかを書いてます。

SRM625Div1Easy

問題

長さN( N \leq 50)の文字列が与えられる。文字列の順番を入れ替えて新しい文字列を作成する。新しく作成した文字列の集合(最初の文字列も含む)からランダムに値を取り出す。その文字列が回文になっている確立を求めよ。

解法

文字列の集合の要素数は順列を用いることで計算できる。出現文字の集合は多重集合(multiset)になるので以下の式となる。
 N! \displaystyle{ \sum_{i=0}^{M} \frac{1}{m_i} }
Nは文字列の長さ、 m_iは各文字の出現回数、Mは出現する文字の集合の要素数とする。
回文となる文字列の数は、出現文字の多重集合を半分に分けた集合を用いて順列の計算を行うことで求まる。分割できるかどうかは、以下の条件を確認することでできる。
Nが偶数: 各文字の出現回数が偶数
Nが奇数: ひとつの文字の出現回数が奇数で他は偶数

計算量

 O(NM)
N: 長さ
M: アルファベットの数

コード