結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー rsk0315
提出日時 2019-08-14 11:23:43
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 2,047 bytes
コンパイル時間 117 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-09-19 13:44:32
合計ジャッジ時間 715 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#! /usr/bin/env python3
from fractions import Fraction
def dot(x, y): return sum(xi * yi for xi, yi in zip(x, y))
def norm(x): return sum(xi * xi for xi in x)
def gso(g, r, u):
    n = len(g)
    for i in range(n):
        for j in range(i):
            u[i][j] = dot(g[i], r[j]) * Fraction(1, norm(r[j]))
        r[i] = g[i]
        for j in range(i):
            r[i] = [rik - u[i][j]*rjk for rik, rjk in zip(r[i], r[j])]
    return g, r, u
def reduce_basis(f):
    n = len(f)
    g = [[Fraction(fij) for fij in fi] for fi in f]
    r = [[0] * n for i in range(n)]
    u = [[0] * i for i in range(n)]
    g, r, u = gso(g, r, u)
    half = Fraction(1, 2)
    i = 1
    while i < n:
        for j in range(i-1, -1, -1):
            if abs(u[i][j]) < half: continue
            f0 = u[i][j] + half
            c = f0.numerator // f0.denominator
            g[i] = [gik - c*gjk for gik, gjk in zip(g[i], g[j])]
            f[i] = [fik - c*fjk for fik, fjk in zip(f[i], f[j])]
            g, r, u = gso(g, r, u)
        if i > 0 and norm(r[i-1]) > 2 * norm(r[i]):
            g[i-1], g[i] = g[i], g[i-1]
            f[i-1], f[i] = f[i], f[i-1]
            g, r, u = gso(g, r, u)
            i -= 1
        else:
            i += 1
    return f
def hack_hash(mod, base):
    sigma = 26
    n = 16
    while True:
        L = [[0] * n for i in range(n)]
        for i in range(n-1):
            L[i][i+0] = -base % mod
            L[i][i+1] = 1
        L[n-1][0] = mod
        poly = reduce_basis(L)[0]
        if all(map(lambda x: abs(x) < sigma, poly)): break
        n += 4
    while poly[-1] == 0: poly.pop()
    s, t = [], []
    for c in poly:
        s.append(c if c >= 0 else 0)
        t.append(0 if c >= 0 else -c)
    return s, t
def main():
    P, B = map(int, input().split())
    s, t = hack_hash(P, B)
    S = ''.join(chr(ord('a')+c) for c in s)[::-1]
    T = ''.join(chr(ord('a')+c) for c in t)[::-1]
    print(S)
    print(T)
if __name__ == '__main__':
    print('baeaaaaaaafaaj')
    print('agafbhabceaaha')
    # main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0