srm668 div1med - らての精進日記

えーよくわからん

以下、面白くない証明が続きます　誰か読んで

えーなんでこれ450なの(個人的に600くらいある)

まず 0→1と1→0の到達可能性を確認する。

「十分大きなすべてのkに対して、k-routeが存在する」⇔「頂点0を含むすべての閉路について、それらの長さのgcdをとったとき、gcd=1となる」
であることを示す。

⇒の証明:
k>=Kであるすべてのkに対してk-routeが存在するとする。するとk>=Kについて、k-walkが存在する。
したがって、k>=2*Kを満たすすべてのkについて、0を含む閉路を構成できる。
したがって、それらの長さのgcdは1である

⇐の証明:
仮定より、あるKが存在して、k>=Kなるすべてのkに対して、長さkの0を含む閉路を構成できる。
そこで、0→1パスを適当に1つとってきて、その長さをpとすれば、k>=K+pなるすべてのkに対して0→1のk-walkが構成できる。
また、1→0パスを適当にとってきて上記と同じようなことをすれば、十分に大きなすべてのkに対して1→0のk-walkが構成できることもわかる。

したがって、各閉路の長さのgcdを求めればよくなった。
しかし、どの程度の長さの閉路まで見ればよいのだろうか。以下では、2*N以下くらいまで見ればよいことを示す。
(しかし、N+3あたりまで見るだけでACする。N+1とかだとWAなので、おそらくテストケースが弱いだけだと思う(そう信じたい))

補題:「0を含む閉路の長さのgcdが1」⇔「0が属している強連結成分内の、(0を含むとは限らない)単純閉路の長さのgcdが1」
前者をp、後者をqとおく。p=1⇔q=1を示す。

⇒の証明:
まず、0を含む閉路を適当に1つ持ってきて、その長さをLとおく。この閉路は、いくつかの単純閉路に分割できる。
それぞれの単純閉路の長さは、qの倍数である。したがって、それらの長さの総和であるLもqの倍数である。
pは、あらゆる0を含む閉路についてのLのgcdであるから、当然pもqの倍数である。
よって、p=1⇒q=1である。

⇐の証明:
強連結成分内のすべての頂点を通る閉路をとってきて、Cとおく。
Cに、適当に単純閉路をくっつけると、十分大きなすべてのkに対して、長さkの0を含む閉路が作れる。
よって、p=1となる。

"雪だるま閉路"という言葉を導入する。これは、次のようなものである。
まず0を含む単純閉路Cを任意に1つ固定する。
このとき、Cは雪だるま閉路であるとみなす。
また、Cが含む頂点の1つから、新たに別の単純閉路を生やしてできる閉路をC'とおく。このとき、C'もゆきだるま閉路であるとみなす。
以上のみが雪だるま閉路である。
雪だるま閉路全体の集合をYとする。また、0を含む閉路の集合をXとする(今知りたいのは、gcd(X)=1かどうか)
ここで、gcd(Y)=1であるならば、Y⊆Xより、gcd(X)=1となる。
gcd(Y)=p(>1)である場合を考える。このとき、0を含む単純閉路の長さはすべてpの倍数であることがわかる。
Y内のゆきだるま閉路のうち、2つの単純閉路の和によってつくられたものを任意にとり、Aとおき、
Aは2つの単純閉路C0とCの和であるとする(C0は0を含む単純閉路 Cはただの単純閉路)

はpの倍数で、

もpの倍数で、

であるから、

もpの倍数。

↑なんかはてな記法のせいで面白いことになった　これ面白くないですか　僕は声を出して笑いました　嘘ですけどニヤッとしました

↓こっちが正しいやつ
size(C0)はpの倍数で、size(A)もpの倍数で、size(C0)+size(C)=size(A)であるから、size(C)もpの倍数

この論法で、すべての単純閉路がpの倍数であるということが言える。
以上より、ゆきだるま閉路のgcd=1⇔単純閉路のgcdが1
であることがわかった。

ゆきだるま閉路は、長さが高々2Nであるから、dp[i][j]:= 長さがiで、最後の頂点がjであるような、頂点0から始まるwalkがあるか？
というdpを、i<=2Nの範囲で計算すれば、O(N(N+M))で解ける。