3/19 PKU

2890 Matrix Multiplication

K*Kの正方行列がある。対角成分はすべて1である。その他にM個の1である成分の位置が与えられる。K^2007において、1が何個あるかを求めよ。但し、ここでは「0+0=0,0+1=1,1+0=1,1+1=1」「0*0=0,0*1=0,1*0=0,1*1=1」とする。

行列A,Bがあるとき、A(p, q)==1 かつ B(q, r)==1ならA*B(p, r)==1となることがわかる。さらに、対角成分は何乗しても残ることがわかるので、Aをかけても1は減らないこともわかる。
ここで、行列Aに対して、「A(p, q)==1なら頂点p→qの辺がある有向グラフ」を考えたとき、「K^2007(p, q)==1」と「頂点pから頂点qへ2007個以下の辺を通って到達できる経路がある」は同値であることがわかる。K<=1000より、2007個も辺を通る必要はない。よって、「頂点pから頂点qへ到達できる、(p, q)の組」の数を求めればよい。これは簡単にDFSによってO(KM)で求められる。
もっと高速な手法としては、行列に対応するグラフを強連結成分分解して答えを求める方法があるだろう。これだとO(K+M)で求められると考えられる。