yukicoder No.1400 すごろくで世界旅行 - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

${V}$ 頂点の重み無し有向グラフの隣接行列が与えられる．任意の頂点 ${i}$ から任意の頂点 ${j}$ までちょうど ${D}$ 本の辺を辿って行くことのができるか判定せよ．

${1\leq V\leq 2000\\ 1\leq D\leq 10^{18}}$

思考の流れ

yukicoder No.1340 おーじ君をさがせとほぼ同じ問題だから行列累乗で終わりと思いきや制約がきつい．

${\downarrow}$

きつくてもゴリ押す．bitsetを用いると，64倍くらい高速になるらしい．また， ${2V}$ 回の移動でたどり着けないようなところは ${D}$ 回の移動を行ってもたどり着けない．だから ${D\leftarrow\min(2V,D)}$ として計算する．計算量は公式解説の計算量に ${\log}$ がつくくらい．かなりギリギリ(現在(2021/02/21)のAC者のなかで)最遅．C/C++以外なら通らないかも