Computing a polynomial hash on the string s. My solution (Horner's method):
base= int(input())
mod= int(input())
s= input()
first_expr= ord(s[0]) * base + ord(s[1])
for i in range(2, len(s)):
first_expr= first_expr * base + ord(s[i])
print(first_expr % mod)
# 123 
# 100003 => 6080
# hash 
How can I speed up this solution?

Answer # 1
Module (
%
) must be called in a loop. Your algorithm now has quadratic complexity. Number of digitsfirst_expr
grows in proportion to the length of the string. Arithmetic operations with it are correspondingly slowed down. This is imperceptible on short lines, but on long lines it will not be good.def phash(base, mod, s): h= 0 for c in s: h= (h * base + ord(c)) % mod return h base= int(input()) mod= int(input()) s= input() print(phash(base, mod, s))
understood thanks. Your solution is indeed faster, but still fails on some tests
Came Up20220129 23:34:20 
Answer # 2
Module (
%
) must be called in a loop. Your algorithm now has quadratic complexity. Number of digitsfirst_expr
grows in proportion to the length of the string. Arithmetic operations with it are correspondingly slowed down. This is imperceptible on short lines, but on long lines it will not be good.def phash(base, mod, s): h= 0 for c in s: h= (h * base + ord(c)) % mod return h base= int(input()) mod= int(input()) s= input() print(phash(base, mod, s))
understood thanks. Your solution is indeed faster, but still fails on some tests
Came Up20220129 23:34:20
 python : Bot on aiogram does not see the answer to someone else's message
 How to translate into a normal format a date from numbers. Python
 Program for finding synonyms of Russian words python
 javascript : How to pass value of js variables to python(eel)?
 python : How to create a window in the game for example (dota2)
 python : Sending a file using telegramAPI
 python : Input() constraint (int, float)
 Authorization key before running Python script
 python : Why does list.remove() incorrectly remove elements in a loop?
Give a link to the testing system.
Stanislav Volodarskiy20220130 07:40:57