pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

yukicoder No.329 全射

問題文

http://yukicoder.me/problems/663

解法

次のようなグラフが与えられたとする。

f:id:pekempey:20151222163359p:plain

このとき A1→A4 への任意の全射を構成できる。 たとえば次のような全射を作りたいとしよう。

f:id:pekempey:20151222163545p:plain

これを作るには、A1→A2 の時点で移動を済ませ、それ以降はそのまま右に流すような写像を合成すればいい。

f:id:pekempey:20151222163604p:plain

作り方から分かるように、A1→A4 への任意の全射を合成によって構成できる。

一方 A2→A3 への全射は作れない。これは |A2| < |A3| だから自明。

一般に Ai から Aj への経路の中に、要素数が wj 未満の集合が存在すれば全射は作れず、存在しなければ任意の全射が作れる。

したがって、

  • Ai→Aj全射が構成できるか?
  • Ai→Aj全射は何通りあるか?

が分かれば問題を解くことができる。

構成できるかの判定

Warshall-Floyd や Dijkstra を使えばいい。

全射の総数の求め方

全射の個数はスターリング数から計算できるので、スターリング数を計算しよう。

ちなみに包除原理でも求まる。

こっちだと 200 * 200 * 1000 * log2(1000) 程度のループが回るため多分 TLE する。(自分は TLE した。でも、冪乗を前計算すれば間に合う)。

yukicoder No.329 全射

問題イメージがなかなか捉えられず苦戦。