結果

問題 No.8014 多項式ハッシュに関する教育的な問題
ユーザー chocorusk
提出日時 2022-08-08 19:00:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 32 ms / 5,000 ms
コード長 3,014 bytes
コンパイル時間 73 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-09-19 04:04:10
合計ジャッジ時間 609 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

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])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0