yukicoder No.329 全射
問題文
http://yukicoder.me/problems/663
解法
次のようなグラフが与えられたとする。
このとき A1→A4 への任意の全射を構成できる。 たとえば次のような全射を作りたいとしよう。
これを作るには、A1→A2 の時点で移動を済ませ、それ以降はそのまま右に流すような写像を合成すればいい。
作り方から分かるように、A1→A4 への任意の全射を合成によって構成できる。
一方 A2→A3 への全射は作れない。これは |A2| < |A3| だから自明。
一般に Ai から Aj への経路の中に、要素数が wj 未満の集合が存在すれば全射は作れず、存在しなければ任意の全射が作れる。
したがって、
が分かれば問題を解くことができる。
構成できるかの判定
Warshall-Floyd や Dijkstra を使えばいい。
全射の総数の求め方
全射の個数はスターリング数から計算できるので、スターリング数を計算しよう。
ちなみに包除原理でも求まる。
こっちだと 200 * 200 * 1000 * log2(1000) 程度のループが回るため多分 TLE する。(自分は TLE した。でも、冪乗を前計算すれば間に合う)。
問題イメージがなかなか捉えられず苦戦。