Employ the trick used in Java, C, and C++, where we terminate an OR early if one its terms is $1$. The probability that one of the terms in each row-column product is $1/k^2$; hence, the expected time for any row-column product is constant. Therefore, the expected running time of the entire product of $A$ and $B$ is $O(n^2)$. If $k$ is $n$, on the other hand, then the probability than an entry in a row-column product is $1$ is $1/n^2$; hence, the expected running time for a row-column product is $O(n)$ in this case. That is, in this case, the expected time to multiply $A$ and $B$ is $O(n^3)$.