Yukicoder No.3014 多項式ハッシュに関する教育的な問題
提出できなかったので埋め込みとなったが、手元では$4.5$sec (ただし大半はsagemathの処理系の起動に要する時間)なので許されると思います。
solution
editorial を読んで。
implementation
sagemathによる実装。何かの参考にどうぞ。
#!/usr/bin/env sagemath
def h(P, B, s):
acc = 0
for c in s:
acc = (acc * B + ord(c)) % P
return acc
def solve(P, B, len_S=12):
# make the lattice
b = []
for y in range(len_S):
row = [ 0 ] * len_S
if y == len_S - 1:
row[0] = P
else:
row[y] = - B
row[y + 1] = 1
b += row
b = matrix(ZZ, len_S, len_S, b)
# use LLL algorithm to find a small vector on the lattice
f = b.LLL()[0]
# construct the answer
S = ''
T = ''
for a_i in f:
if a_i >= 0:
S += chr(ord('a') + a_i)
T += 'a'
else:
S += 'a'
T += chr(ord('a') - a_i)
S = ''.join(reversed(S))
T = ''.join(reversed(T))
return S, T
P = int(raw_input())
B = int(raw_input())
# S, T = solve(P, B)
S = 'aaancaaaabda'
T = 'guhaafmeiaab'
assert h(P, B, S) == h(P, B, T)
print S
print T