No.162
独立した歯同士はお互いに影響を与えないので, 連続した歯についてのみ考えればいい.
80歳まで残り \(i\) 年で, 残り \(j\) 本の連続した歯があるときの80歳時に残っている歯の本数の期待値を \(E(i, j)\) とする.
そうすると,
\[E(i, j) = \sum_{m \in M} \left( p(j, m) \sum_{c \in C} E(i-1, c) \right)\]となる. ここで, \(M\) は \(j\) 本の連続した歯の集合の部分集合すべてであり, ビットで表現する. \(p(j, m)\) は \(j\) 本の歯が \(m\) になる確率であり, これはあらかじめ計算しておく. \(C\) は \(m\) に含まれる連続した歯の本数を配列で表したものであり, これもあらかじめ計算しておく.
DP で上記の漸化式を計算する. \(2 \times E(80-A, 14)\) が答えとなる.