Auto comment: topic has been updated by pranjal.ssh (previous revision, new revision, compare).

I dont remember all the details but my solution went like this:

Let's represent colors of cats as vector v. As you noticed two cats talking and changing color can be described using linear equations. So let's find matrix M such that v multiplied by M equals vector of cat colors after one step. Thus colors after k steps are v*M^k. This yield O(n^3 log k) solution but one can notice that matrix M is special. It's something like: value of every cell thats not in first 2 rows and first 2 columns is equal to value of north-west neighbouring cell. So every matrix is characterized only by its first 2 rows and first 2 columns and it turns out that their multiplication is actually just a few convolutions which can be done using FFT in O(n log n) so total complexity becomes O(n log n log k).