結果
問題 | No.3014 多項式ハッシュに関する教育的な問題 |
ユーザー | kokoa1046 |
提出日時 | 2018-01-30 19:46:09 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 821 bytes |
コンパイル時間 | 41 ms |
コンパイル使用メモリ | 6,784 KB |
実行使用メモリ | 6,816 KB |
最終ジャッジ日時 | 2024-06-09 11:51:53 |
合計ジャッジ時間 | 513 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ソースコード
#!/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 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) a = b.LLL()[0] S = '' T = '' for a_i in a: 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