?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
полиномиальный хеш aka кольцевой хеш Рабина-Карпа aka хеш для олимпиад...
nyaload
_winnie
при использовании "естественного" модуля 2^64 ломается вот таким неожиданно красивым образом:
http://codeforces.com/blog/entry/4898
Tags: ,

  • 1
Всё весьма просто - чтобы использовать хеш по модулю M обычно нужно не бояться, что число порядка M^2 влезет в стандартный тип данных(на олимпиадах сейчас таковым самым большим считается 64битный), иначе будет переполнение, когда попытаемся что-то перемножить. 2^64 было очень удобным потому, что о переполнении можно не беспокоиться, оно автоматически правильно возьмется по модулю.

В итоге теперь нужно пользоваться двумя разными модулями и вместо стандартного переполнения 64битного числа вручную вызывать операцию деления с остатком, что напрочь убивает всю производительность.

  • 1