Path counting exponentiation

Adj^k counts length-k walks.

Try this in Python

adj = [[0, 1], [1, 0]]

def mul(a, b):
    return [[sum(a[i][k] * b[k][j] for k in range(2)) for j in range(2)] for i in range(2)]

print(mul(mul(adj, adj), adj))

Key takeaways

• Walk vs path.
• Mod walks.
• Sparse doubling advanced.