ABC212 E - Safety Journey - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点の完全無向グラフから ${M}$ 辺取り除く．このグラフの頂点 ${1}$ から ${K}$ 本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点 ${1}$ であるようなパスの数を求めよ．

${2\leq N\leq 5000\\ 0\leq M\leq \min(\frac{N(N-1)}{2},5000)\\ 2\leq K\leq 5000}$

解説

頂点 ${i}$ から頂点 ${j}$ への長さ ${K}$ のパス(厳密にはwalk)の数は，グラフの隣接行列を ${K}$ 乗した行列の ${(i,j)}$ 成分と一致する．
ja.wikipedia.org

これを用いると今回の問題では，グラフの隣接行列を ${K}$ 乗した行列の ${(1,1)}$ 成分が求めるものとなる．このまま適用すると，隣接行列は ${N×N}$ の行列なので ${O(N^3\log{K})}$ かかって間に合わない．

${\downarrow}$

補グラフの隣接行列を見ると ${M}$ 個の非零成分のみからなる疎行列になっている(この行列を ${A}$ とする)．また，全成分が ${1}$ の ${N×N}$ 行列を ${P}$ ，単位行列を ${I}$ とすると，元のグラフの隣接行列は ${P-I-A}$ と表される．
したがって， ${(P-I-A)^K}$ の ${(1,1)}$ 成分が答えとなる．第 ${1}$ 成分のみ ${1}$ であり，他の成分が ${0}$ であるような列ベクトル ${v\in\mathbb{R}^N}$ を用いると ${v^{\top}(P-I-A)^Kv}$ と書ける．

分かりづらいと思うので例(入力例3)

入力例3において
グラフの隣接行列 ${ \left( \begin{array}{ccccc} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right)}$

補グラフの隣接行列 ${A= \left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)}$

${P= \left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{array} \right)}$

${I= \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right)}$

${v= \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0 \end{array} \right)}$

求めるものは
${v^{\top}(P-I-A)^Kv= \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \end{array} \right) \left( \begin{array}{ccccc} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right)^K \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0 \end{array} \right)}$

${(P-I-A)^K}$ を計算する代わりに右から順に ${(P-I-A)x, x\in \mathbb{R}^N}$ を計算していく．

${Px}$ は ${P}$ の全ての行が同じなので ${O(N)}$ で計算できる．
${(I+A)x}$ は ${I+A}$ の非零成分が ${N+2M}$ 個なので， ${O(N+M)}$ で計算できる(詳しくは下の実装)．
よって， ${(P-I-A)x}$ は ${O(N+M)}$ で計算できる．これを ${K}$ 回繰り返すので ${O((N+M)K)}$ で解ける．