Let's fix a block of the crossword. We can assume that we always choose the initial letter from that block. Probability is defined as the number of favorable selections divided by the number of possible selections. The number of possible selections of two words is equal to the square of the number of possible selections of one word, and it is equal to the number of possibilities for the initial field (~M \times N~) multiplied by the number of possible directions (~8~).

A bigger issue is calculating the number of favorable selections, the ones that provide two equal words. If a word ~R~ appears in ~X~ possible places, then we can read it once in ~X~ ways, and twice in ~X^2~ ways. Therefore, it is necessary to add up the squares of these numbers ~X~, or, more precisely, to identify different possible words and know in how many ways each of them can be read.

We do this by using a hash function that converts a string to a number for easier comparison. Hashing is problematic here because of the size of ~K~ (the length of the word). In the case where ~M = N~, we can notice that all words are periodic with regards to period ~N~, so it is sufficient to look at length ~K \mathbin\% N~, and all such hashes can be calculated fast enough using the rolling hash approach. This solution was worth 100 points.

In the general case, we can, as an auxiliary step, calculate all hashes which length is a power of ~2~, so that the hash of length ~2^{i+1}~ is obtained by combining two hashes of length ~2^i~. Then we write ~K~ in binary as the sum of powers of ~2~. This way, we calculate the hash of each possible word as a combination of a couple of already calculated hashes. We can determine the number of times each of them appears by sorting the set of hashes of possible words and therefore obtain the required probability.