解説

$f(i, j) :=$ 人間$i$人，人狼$j$匹の状態から始めたときの，事件が起こらなくなった時点での生存している人間の期待値

とします．

事件が起こらなくなる条件は，$j=0$または$i \leq j \land 0 < j$です．このとき，以下が成り立ちます．

$f(i, 0) = i$

$f(i, j) = 0 (i \leq j \land 0 < j)$

遷移は，以下のようになります．

$f(i, j) = \left\{ \begin{array}{ll} f(i - 1, j) & (i + j \equiv V + W (\bmod 2))\\ \cfrac{i}{i + j}f(i - 1, j) + \cfrac{j}{i + j}f(i, j - 1) & (else) \end{array} \right.$

$f(V, W)$が求める答えで，計算量は$O(VW)$です．