No.041 D

$x_i \rightarrow y_i$ となる有向辺を持つグラフを考える.

このとき, 1位になる可能性があるのは入力辺を持たない頂点である. この頂点集合を $C$ として, 頂点集合 $S$ を並べる組み合わせの数を $A(S)$ とすると,

$$A(S) = \sum_{i \in C} A(S \setminus i)$$

となる. ただし, $A({i}) = 1$ である. これをメモ化再帰で計算する.