E - Transition Game

出次数1の有向グラフ上を移動すると考えることができます。出次数1のグラフは、「各連結成分について、閉路をただ1つだけ持ち、全ての頂点から有向辺を辿ると閉路に辿り着く」ことが言えます。

そこで、まず高橋くんが青木くんを閉路上の頂点に行かせたい場合を考えます。
$m$ 頂点からなる閉路について、任意の頂点から移動を開始して辿り着いた順に $0,1,\cdots ,m-1$ と番号をつけます。

番号 $s$ から開始して、 $k$ 回移動した場合に最後にいる頂点の番号は、 $(s+k)\ mod\ m$ で計算できます。

青木くんが移動回数 $K_i$ を指定した場合を考えます。高橋くんが移動を開始する頂点番号 $S_i$ を指定し、頂点 $X$ に行かせたいとすると、

$S_i + K_i \equiv X\ mod\ m$

という合同式から、

$S_i$ を $(X-K_i)\ mod\ m$ にすれば良いです。
このことから、閉路上の任意の頂点については、青木くんの指定に対して、高橋くんは青木くんを必ず行かせたい頂点に行かせることが可能です。よって、高橋くんの勝ちとなります。

閉路でない部分の頂点に行かせたい場合を考えます。例えば青木くんが $K_i$ を $10^{100}$ などとすれば必ず閉路に行き着くため、高橋くんは開始の頂点をどのように指定しても勝つことはできず、青木くんが勝ちます。

以上から問題の答えは、各連結成分についての、閉路に属する頂点数の合計です。
閉路に属する頂点数が2個以上なら強連結成分分解で得ることができます。また、頂点数が1個の閉路、すなわち自己ループは、 $A_i = i$ かどうかで判定できます。

ユーザ解説によれば、出次数1の有向グラフをfunctional graphと呼ぶらしいです。

geam1113’s diary