yukicoder #562: 超高速一人かるた small
p(T)を
読み上げられたカードの集合がTであるときのパターン数とする。
p(Φ) = 1
p(T(!=Φ)) = Σ[i ∊ T] ( p(T-{i}) )
で簡単に求まる。
e(T)を読み上げられたカードの集合がTであるときの
期待値 と パターン数の積とする。
E[K] * P[N,K] = Σ[T⊆読み札, |T|=K](e(T))
が成り立つ。
これらは、すべてのパターンについて、読み上げられた文字の数の和をとったもの。
なので、
e(T)
= Σ[j∊T](e[T-{j}] + p[T-{j}] * (T-{j}の後でjの読み札を見たときの読み上げる文字数)
で求まる。
T-{j}の次がjとして、そのとき読み上げられた文字数を求めるには、事前に
f[i][j] = iをjと区別するのに必要な最低の読み上げ文字数
を計算しておけば楽。これは愚直に求められる。
L = max(|S[i]|)として
事前計算でO(LN^2), DPの計算にO(2^N * N^2)の時間で間に合う。