Появилась 1 довольно просто задача проверки всех возможных путей.Однако оказалось, что не всё так просто. Подзадачей к этой задаче является нахождение хэша матрицы 6 х 6 с коллизией -> 0. Я долго исказл в гугле хорошие реализации этих хэш функций, так же сам думал над разными алгоритмами, однако все они вылетали на похожих тестах.
Очень хотелось бы узнать какой нибудь новый алгоритм или идею, которая поможет находить хэш такой матрицы.
А обычный полиномиальный ( с основанием больше макс.значения) тоже легко валится? Что-то странно мне это кажется.
Матрица из целых чисел? Какие ограничения на числа в матрице. Возьмите два основания — одно по строкам, второе по столбцам.
если не сработает такое, попробуйте найти простое число P порядка 1018 и считайте хеш именно по основанию P. Только не забывайте про переполнение(перемножайте в даблах).
Расскажи как в даблах перемножить и поделить с остатком. Перемножить два 64-х битных числа по модулю 63-х битного можно в целых числах рекурсивной процедурой наподобие функции pow (powering by squaring)
Скорее всего он имел в виду это.
Кроме того, проще посчитать несколько хешей по разным модулям в районе 32-х бит
Как удобным образом считать хеш по такому основанию? Считать (X*BASE+Y)%MOD бинарным умножением? Той же точности можно достичь, считая по основанию пары различных простых порядка 109, без каких-либо проблем с переполнением.
И вопрос к goo.gl_SsAhv: зачем нам пара различных простых BASE0 и BASE1? Достаточно одного. Если нужно вот так втупую посчитать хеш одной подматрицы, то это все равно что посчитать хеш строки длиной 6*6. Если посчитать частичные суммы по всей матрице, и потом отвечать на запросы — тоже получим вполне рабочую версию Рабина-Карпа.
link
Про парадокс дней рождения знаешь? тут прочти, и по ссылкам пройди