[AOJ] No. 0386 ワープ装置

問題

方針

\( d(i) \) を文字 \( i \) の出口への行き方の数として、動的計画法を行います。初期値は \( d(s_0) = 1\) とします。更新式は、\( d(s_i) \leftarrow d(s_i) + d(t_i) \ (1 \leq i \leq N – 2)\) です。\( i \) の範囲が \( N – 2 \) までなのは、\( d(s_{N-1}) \leftarrow d(s_{N-1}) + d(t_{N-1}) \) と更新してしまうと、星 \( N \) からさらにワープする場合の数を足してしまうからです。

コード