ある村には人の人間と匹の人狼がいることが分かっています.
人狼の数が人間の数以上になると,その瞬間に全ての人間は人狼に食べられてしまいます.
これから村では「(生存している)人間が人になる」か「(生存している)人狼が匹になる」まで以下の事件が交互に繰り返されます.
襲撃が起こり,人間が一人食べられる.
処刑が起こり,人間または人狼が一人(一匹)減る. 処刑対象は生存している人間または人狼から無作為に選ばれる.
事件が起こらなくなった時点で生存している人間の数の期待値を求め,で出力してください.
より正確には,期待値が有理数,つまりある既約分数で表されること,さらにを満たす整数が一意に定まることがこの問題の制約より証明できます.よって,このを出力してください.
入力はすべて整数である.
期待値をで出力せよ.
3 1
665496236
以下のように人数が変化します.
まず襲撃が起こり,人間は人,人狼は匹になります.
次の処刑では,
したがって,生存している人間の数の期待値はです.で出力することに注意してください.
3 3
0
1999 1
666