Блог пользователя pksingh290

WA on codeforces round 166 prob d(Hashing)
Автор pksingh290, история, 6 лет назад, По-английски

i am using string hashing in the sollution but each time i m getting WA on submission .i am unable to find where it went wrong . all the suggestions to make the sollution correct are welcome .here is the link to the sollution https://codeforces.me/contest/271/submission/85804655

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Your hash was too weak. I fixed your code by using p2 = 29 and making the hashes pairs of long longs: 85813439

P.S. The code became much faster after using vector and unique instead of set: 85813494. set's constant factor is huge compared to vector.

Also if the string size is bigger or stores a wider range of characters, the hashes of substrings will overflow long long, so you should hash under two moduli (1e9 + 7 and 1e9 + 9 worked for me).

→ Ответить