We found that case by accident during that POI :) We actually submitted a short paper about this to the next IOI journal.

You are talking right things. Hash value of order 10^9 + 7 can really cause collisions. But it's useful to understand why exactly collision can happen.

Imagine the problem, where you are asked to check 10⁵ pairs of substrings of big string to be equal. Suppose that answers for each query are in fact "NO". Let's assume that due to big length hash of each substring is random uniformly distributed value over segment [0..10⁹ + 6] not depending from hashes of other strings. Then the probability that the check suddenly gives us answer "YES" instead of "NO" is almost same with the probability of two uniformly distributed values from that segment to be equal. This probability is 10^- 9. The probability that no one of the 10⁵ checks will fail due to collision is (1 - 10^- 9)¹⁰⁵ ≈ 1 - 10^- 4, that is really close to 1. One the testset consisting of 100 tests the probability that you'll recieve "Accepted" is (1 - 10^- 4)¹⁰⁰ ≈ 99%. That's pretty big probability to write such solution, so using single hash modulo 10⁹ + 7 is ok for that type of problems.

Other type of problems involve checks like "check that hashes of 10⁵ substrings are pairwise different". For example if we calculate number of different substrings of length 5·10⁴ in string of length 10⁵ and they all are in fact different. Once again, we can assume that each hash of that substrings is random uniformly distributed value from segment [0..10⁹ + 7], that are independent one for each other. So now we need to calculate another probability: that from 10⁵ random integers from range of length 10⁹ no two will suddenly coincide, giving as less answer then expected an verdict "Wrong Answer".

But here appears the effect known as Birthday problem: surprisingly, but for different independent randomly distributed values probability for some pair of the to be equal is about . So for 10⁵ probes our probability to fail on one test will be even greater than 50%!

Here is one note: we take hash over prime modulo because for prime p Z_p is a field, and for finite fields it can be proven, that all values above (that are values of random polynomials in fixed point) are very close to be really uniformly distributed over the whole field. If we take composite number, there will appear special effects like zero divisors and other, so there is needed additional analysis of probability for that cases, it can easily happen that all such calculations for them will be wrong. The main idea of my topic is exactly about surprising property of Z_2⁶⁴, that one can easily build a polynomial of small degree (~2048), whose value is zero in any point, so it isn't suitable for solving problems with hashes.

So as you correctly said, we need to increase the hash-value space size. One way is to look on one hash modulo prime of greater size. But there is indeed a problem with their multiplication. You can multiply them with binary multiplication (such as binary exponentiation, but with adding and doubling on each step), or you can use some hacks like this (examples of code in Russian interface).

Other idea is two use a pair of hashes by two different prime modulo of order 10⁹, let's say, p and q. Then we once again can assume that two components of that hash will be independent of each other random uniformly distributed over the Z_p and Z_q respectively, so in fact we have a point in 2d-space that is randomly uniformly distributed over the p·q ≈ 10¹⁸ possible values. Then in every calculation above we can replace 10⁹ with 10¹⁸ and probability for us to fail becomes insignificant. From my experience this way is faster then previous two.

I hope this will help in understanding, when hashes can cause a collision, and why we can submit correctly proved hash solution and be sure, that it will be Accepted.

But note one other thing. Exactly as Zlobober said there are two types of problems where hashes are useful — comparing many pairs of strings and checking if all hashes are different. Note that when you just check if two hashes are equal or not, you probably won't have to check so many pairs that a probability of a collision will be high, because firstly it will rather exceed time limit than find a collision. In that case exponent in (1-p)^k (where p is a prob. of collision) grows linearly with time of execution. When you have 10^6 hashes generated modulo 10^9 number of colliding hashes will be pretty high but that doesn't change fact that if you won't do more than 10^6 queries of type "==" the probability of FINDING collision is really small (~0.999). This can be stated unless you won't do anything else than using operation "==" or "!=". But when you use other operations such as "<" the exponent and so the probability of collision may grow much faster! Best example is a simple example "are all of those hashes are different". You can sort them and check if every two consecutive values of hashes are different. But in this case you have used a specific values of hashes and that allowed you to obtain O(n^2) informations in O(n log n), so a probability of finding a collision in former example is very large.

So summing up:

1. I use only "==" and "!=" -> nothing to worry about

2. I use "<" (maybe hidden in sort or a set or a map or anything) -> use pair of hashes mod 10^9+7 and 10^9+13 or anything else.

Strings "aab" and "bba" have the same hash value.

Sorry for necroposting, but this is possible to break as well.

I will consider slightly more general construction. Let M be some 2 × 2 matrix with integer coefficients then hash of string s₀s₁... s_n is modulo 2^w (w = 32 or w = 64) — also 2 × 2 matrix.

In your case, for some odd b. One can verify that M² = M + b (b is a shorthand for bE, where E is the identity matrix) holds even in integers, let alone modulo any number (math remark: because M's characteristic polynomial is x² - x - b). One can say that in the following sense if A - B has only even entries. Therefore .

Now we can substitute M³ instead of P in the (P - 1)(P² - 1)... (P^2Q - 1 - 1) expression from the post. One can see that only important quality of P was that P - 1 and P + 1 are both divisible by 2. As shown above, in a sense this still holds for M³. Therefore (M³ - 1)(M⁶ - 1)... (M^{2Q - 1·3} - 1) is a polynomial of M with small degree, coefficients in range [ - 1, 1] and is zero on any matrix of form.

Even more, suppose that M is any 2 × 2 integer matrix with odd determinant (basically, nondegenerate when considered modulo 2). Then . One can verify this by brut force, but probably easier way to see this is (warning: math ahead) is noticing that nondegenerate matrices modulo 2 form a finite group of order 6 and apply [Lagrange's theorem, link is not clickable for some reason](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)#Applications ).

Considering matrices M that are degenerate modulo 2 may complicate things a bit, but this is not the best idea for the same reason as using even P is a really bad idea when using simple polynomial hashes modulo 2^w.

Warning: more math ahead.

One can also ask what will happen if we use 3 × 3, 4 × 4 matrices, et cetera. Well, for 3 × 3 matrices and w = 64 the degree of the resulting polynomial will be 2¹¹·|GL(3, 2)| = 2¹¹·(8 - 1)·(8 - 2)·(8 - 4) = 344064 (you can read about GL(n, p) here), what is slightly more than usual constraints in string problems, but I believe that this can be hacked with more careful consideration of the same idea. And I am not sure that using 4 × 4 matrices will be faster than usual double hashing approach (did not test it though) and it doesn't sound safe either.

TL;DR: strings s and t generated by the following code should have equal Fibonacci hashes modulo 2⁶⁴:

const int q = 11;
const int n = 3 * (1 << q);

string s, t;
for (int i = 0; i < n; i++)
{
    if (i % 3 != 0)
        s += 'a', t += 'a';
    else
    {
        int bit = (__builtin_popcount(i / 3) % 2);
        s += 'a' + bit;
        t += 'a' + (1 - bit);
    }
}