Re: the Princess (ZOJ Problem Set - 3560)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3560

問題

n人の人がいて掲示板に発言を書きこんでいく。それぞれの人はsignatureと発言を持っている。掲示板に発言を書きこむのは直前の発言をした人以外で出てきた人である。次に書きこむ確率は(その人が直前の発言で出てきた回数)/(直前の発言に出ている発言者以外のsignatureの個数)である。0番目の人から発言を開始した時、発言はいくら続くか期待値を求めよ。
1<=n<=100

解法

無限に続くかどうかの判定はdfsで行い、期待値は連立方程式を作ってガウスの消去法で求める。