結果

問題 No.3014 多項式ハッシュに関する教育的な問題
ユーザー rsk0315rsk0315
提出日時 2019-08-14 11:31:30
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,997 bytes
コンパイル時間 83 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-09-19 13:44:39
合計ジャッジ時間 587 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#! /usr/bin/env python3

from decimal import Decimal, getcontext

getcontext().prec = 100

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]) / 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 = [[Decimal(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 = Decimal('0.5')
    i = 1
    while i < n:
        for j in range(i-1, -1, -1):
            if abs(u[i][j]) < half: continue
            c = (u[i][j] + half).to_integral_value('ROUND_FLOOR')

            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__':
    main()
0