問題概要
この問題は，実行時間に占める入出力の割合が比較的大きいです．
本記事内での私の提出では，入出力に 180 ms 程度を要しているようです．実行時間を比べる場合にはこのことに注意してください．
解法
$\Theta\left(\frac{NMK}{w}\right)$ 時間
定義通りの行列積の愚直な計算考えると，$AB=C$ のとき $C[i][k] = \sum A[i][j]B[j][k]$ なので，$A[i][j]=1$ のときにすべての $k$ に対して $C[i][k] += B[j][k]$ をするという処理になります．これは bitset を使って高速化できます．
- 解答例（367ms）
$\Theta\left(\frac{NMK}{w\log N}\right)$ 時間
Method of Four Russians と呼ばれるテクニックによる高速化を紹介します．
適当なバケットサイズ $b$ をとり，区間 $[0,M)$ を長さ $b$ の区間 $M/b$ 個に分割します．各バケットに対して次を行います：
- $L\leq j < R=L+b$ となる $j$ に対して，$C[i][k] += \sum_{L\leq j < R}A[i][j] B[j][k]$ という計算を行う．
bit 列 $(A[i][j]\mid L\leq j < L+b)$ は $2^b$ 通りしかありません．そのような $2^b$ 通りの前計算により，固定された $i$ に対する処理を $\Theta(K/w)$ 時間で行えます．バケット内での前計算は $\Theta(2^bK/w)$ 時間，$C$ への加算は $\Theta(NK/w)$ 時間です．
すべてのバケットに対する計算量の総和は次のようになります．
- 前計算：$\Theta(2^bK/w \times M/b)$ 時間．
- C への加算：$\Theta(NK/w \times M/b)$ 時間．
合わせると $\Theta(MK/w\times ( 2^b/b + N/b))$ となります．$b = \log N$ ととれば，計算量 $\Theta(NMK/w\log N)$ が達成されます．
- 解答例（212ms）
個人的に Method of Four Russians は実装量の割に恩恵が少ないことが多いという印象を持っていましたが，これは実装量の少なさ，実行速度の速さのどちらの意味でもかなりおすすめできると思いました．
