CodeForces Contest #51 E

題目: Given an undirected simple graph, count the numbers of length-5 cycle
|V| ≤ 700, time limit = 10s

看規模應該可以用 O(V³) 的方法 solve
Compute A⁵, A 為 G 的 adjacency matrix
所以 tr(A⁵) 便是 G 的 length-5 closed walk 的數目
但是想要的是 cycle, 所以要減去不是 cycle 的 length-5 closed walk
可以在 O(V³) 內 count 到

但是 time limit 還是很緊, 所以還要繼續優化
首先注意到 A^k 是 symmetric 的, 可以減少約一半的乘法數目
以及因為只用到 A⁵ 的 trace, 所以只需做 2 次的 full matrix multiplication

其實我的做法不是最好的, 看到有些人 consider A⁴
好處是 A⁴ 不需要使用 long long