【今日の精進】ARC150D - Removing Gacha

毎日格上の問題を倒すやつの12日目です。

問題リンク

atcoder.jp

問題概要

全部の頂点が白い木があるよ。

「頂点 からのパスの中に白い頂点があるような頂点を つ黒く塗る」ことを繰り返してすべての頂点を黒くするときの回数の期待値を答えてね。

解法

期待値の線形性定期です。すべての頂点の期待値を足します。

頂点 からの距離が等しいところは明らかに期待値が同じなので、距離ごとに考えます。

距離が の点は明らかに です。そのあとはどうなるでしょうか。

距離が のところは期待値が 、距離が のところは期待値が のようになることが推測できます。これは、 です。

実験してみると、これは確かにあっています。¹

というわけで、これを実装すれば終わりです。

提出コード

import sys
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit((1<<19)-1)

def dfs(pos,cnt):
    ret=calc[cnt]-calc[cnt-1]
    for i in gr[pos]:
        ret+=dfs(i,cnt+1)
    ret%=MOD
    return ret

MOD=998244353
N=int(input())
p=list(map(int,input().split()))
calc=[1 for i in range(N+1)]
calc[0]=0
for i in range(2,N+1):
    calc[i]=(calc[i-1]+1+calc[i-1]*pow(i,-1,MOD))%MOD
gr=[set() for i in range(N)]
for i in range(N-1):
    gr[p[i]-1].add(i+1)
print(dfs(0,1))

Submission #46150820 - AtCoder Regular Contest 150

感想

Q.期待値の線形性の難問しか解けない人ですか？

A.フローの難問も解けます。

---

1. 未証明です(え？)↩