概要
素直に $O(N\log N)$ 時間になるので一応書きます．
$p=x/100$, $q=1-p$ とします．
$N$ 頂点の有向グラフを，各 $(i,j)$ について確率 $p$ で辺を張ったときに，頂点 $0$ から到達可能であるような頂点数の期待値を求める問題です．
解法
$p\neq 1$ を仮定します．
非負整数 $n$ に対して，$a[n]$ を次のように定めます：
- 頂点 $0,1,\ldots,n+1$ に辺を張るときに，全頂点が $0$ から到達可能である確率．
$1$ から条件を満たさないものを引くことで立式します．$0$ から到達可能である頂点全体が $0$ を除きちょうど $m$ 個であるものは，次の積です：
- $\binom{n}{m}$：どの $m$ 頂点かを選ぶ
- $a[m]$：選んだ $m$ 頂点と頂点 $0$ を合わせて辺を張り，$m$ 頂点に到達可能であるようにする
- $q^{(m+1)(n-m}}$：到達可能とした $m+1$ 頂点から選ばれなかった $n-m$ 頂点への辺は全部辺が張るられないようにする．
これで，次のような式ができます：
$$a[n]=1-\sum_{m=0}^{n-1}\binom{n}{m}a[m]q^{(m+1)(n-m)}. $$
次のように書き替えられます．
$$\sum_{m=0}^{n}\binom{n}{m}a[m]q^{(m+1)(n-m)}=1. $$
これは $\sum A[m]B[n-m]=C[n]$ の形の式に変形できます．
二項係数部分は $\frac{n!}{m!(n-m)!}$ となおして両辺を $1/n!$ 倍すればよいです．$q$ のべき乗部分は，$(m+1)(n-m) = \binom{n+1}{2}-\binom{m+1}{2}-\binom{n-m}{2}$ と変形すればよいです．この式変形は巧妙に感じられるかもしれませんが，$n+1$ 頂点間の無向辺の個数から $m+1,n-m$ 頂点のグループ間の無向辺の個数を引くと考えればよいです．
$A[n]B[n-m]=C[n]$ かつ $B,C$ が既知という状況になれば，形式的べき級数除算により $A$ が求まり，$a[0], \ldots, a[N-1]$ が求まります．ここから答を求めるのは簡単です．
