There is a problem that I solved earlier: Find how many permutations p s.t. $$$|p_i-i|\leq k$$$ for all $$$i$$$. Constraints: $$$n<=10^9,k<=4$$$. I solved it using matrix multiplication, but naively multiplying the matrix creates the insane complexity of $$$O(64^k*\log(n))$$$. By skipping the non-zero terms in the left hand side, I was able to get it passed. Can anyone explain why this passes, and maybe prove the complexity of it?