結果

問題 No.3014 多項式ハッシュに関する教育的な問題
ユーザー chocoruskchocorusk
提出日時 2022-08-08 19:49:29
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 3,125 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-09-19 04:41:38
合計ジャッジ時間 566 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

loop=0
def LLL(b, eta_n=501, eta_d=1000, delta_n=99, delta_d=100):
    k = 2
    kmax = 1
    n = len(b)
    m = len(b[0])
    d = [0] * (n+1)
    d[0] = 1
    d[1] = sum(b[0][_]*b[0][_] for _ in range(m))
    # H = [[1 if j==i else 0 for j in range(n)] for i in range(n)]
    lmd = [[0]*n for _ in range(n)]

    def RED(k, l):
        if -eta_n*d[l]<=eta_d*lmd[k-1][l-1] and eta_d*lmd[k-1][l-1]<=eta_n*d[l]:
            return
        q = (2*lmd[k-1][l-1]+d[l])//(2*d[l])
        # for i in range(n):
        #     H[k-1][i] -= H[l-1][i]*q
        for i in range(m):
            b[k-1][i] -= b[l-1][i]*q
        lmd[k-1][l-1] -= q*d[l]
        for i in range(l-1):
            lmd[k-1][i] -= q*lmd[l-1][i]

    def SWAP(k):
        # # swap(H[k], H[k-1])
        # for i in range(n):
        #     tmp = H[k-1][i]
        #     H[k-1][i] = H[k-2][i]
        #     H[k-2][i] = tmp

        # swap(b[k], b[k-1])
        for i in range(m):
            tmp = b[k-1][i]
            b[k-1][i] = b[k-2][i]
            b[k-2][i] = tmp
        
        if k > 2:
            for j in range(1, k-1):
                tmp = lmd[k-1][j-1]
                lmd[k-1][j-1] = lmd[k-2][j-1]
                lmd[k-2][j-1] = tmp
        v = lmd[k-1][k-2]
        B = (d[k-2]*d[k]+v*v)//d[k-1]
        for i in range(k+1, kmax+1):
            t = lmd[i-1][k-1]
            lmd[i-1][k-1] = (d[k]*lmd[i-1][k-2]-v*t)//d[k-1]
            lmd[i-1][k-2] = (B*t+v*lmd[i-1][k-1])//d[k]
        d[k-1] = B

    def test_LLL_condition(k):
        global loop
        loop += 1
        RED(k, k-1)
        if delta_d*d[k]*d[k-2]<delta_n*d[k-1]*d[k-1]-delta_d*lmd[k-1][k-2]*lmd[k-1][k-2]:
            SWAP(k)
            if k > 2:
                k -= 1
            k = test_LLL_condition(k)
        else:
            for l in range(k-2, 0, -1):
                RED(k, l)
            k += 1
        return k

    while k <= n:
        if k <= kmax:
            k = test_LLL_condition(k)
        else:
            kmax = k
            for j in range(1, k+1):
                u = sum(b[k-1][_]*b[j-1][_] for _ in range(m))
                for i in range(1, j):
                    assert (d[i]*u-lmd[k-1][i-1]*lmd[j-1][i-1])%d[i-1]==0
                    u = (d[i]*u-lmd[k-1][i-1]*lmd[j-1][i-1])//d[i-1]
                if j==k:
                    d[k] = u
                    assert d[k] != 0
                else:
                    lmd[k-1][j-1] = u
    
    #print(loop)
    return b


p=1000000000000000003
b=123456789987654321

n=11

mat=[[0]*n for _ in range(n)]
for i in range(n-1):
    mat[i][i]=-b
    mat[i][i+1] = 1
mat[n-1][0]=p

# res=LLL(mat, 1, 2, 3, 4)[0]
res = LLL(mat)[0]
#print(res)

s=[]
t=[]
for i in range(n):
    if res[i]>=0:
        s.append(chr(ord('a')+res[i]))
        t.append('a')
    else:
        t.append(chr(ord('a')-res[i]))
        s.append('a')
s=''.join(s)
t=''.join(t)

hs=0
ht=0
for i in range(n):
    hs+=ord(s[i])*(b**i)
    ht+=ord(t[i])*(b**i)
hs%=p
ht%=p
assert hs==ht

print(s[::-1])
print(t[::-1])
0