結果

問題 No.3014 多項式ハッシュに関する教育的な問題
ユーザー chocoruskchocorusk
提出日時 2022-08-08 19:00:01
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 3,014 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 12,384 KB
実行使用メモリ 10,268 KB
最終ジャッジ日時 2023-10-19 07:46:14
合計ジャッジ時間 856 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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

# loop=0
def LLL(b):
    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 -d[l]<=2*lmd[k-1][l-1] and 2*lmd[k-1][l-1]<=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 4*d[k]*d[k-2]<3*d[k-1]*d[k-1]-4*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=12

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)[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