結果

問題 No.3082 Make Palindromic Multiple(Judge)
ユーザー 👑 binap
提出日時 2025-03-29 08:48:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,729 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 150,012 KB
最終ジャッジ日時 2025-03-29 08:49:02
合計ジャッジ時間 23,525 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 57 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    
    # 入力
    K = int(input())
    blocks = []
    for _ in range(K):
        # 各行は「S T」という形式を仮定
        # もしくは別行で与えられる場合もあるので適宜修正
        line = input().split()
        S = line[0].strip()
        T = int(line[1])
        blocks.append((S, T))
    
    # ハッシュ計算のための定数
    base = 10007
    mod1 = 1000000007
    mod2 = 1000000009
    
    # 拡張ユークリッド互除法による逆元計算
    def modinv(x, mod):
        return pow(x, mod-2, mod)
    
    # 幾何級数の和 : 1 + r + r^2 + ... + r^(T-1)
    def geo_sum(r, T, mod):
        if r % mod == 1:
            return T % mod
        return (pow(r, T, mod) - 1) * modinv(r - 1, mod) % mod
    
    # 各ブロックについて，順方向のハッシュと逆方向のハッシュを計算する。
    # S の各文字は '0'-'9' なので，数値としては 1～10 に変換（'0'を1にする等）
    def compute_hashes(S, mod):
        h = 0
        for ch in S:
            # 数値部分：'0'からのずれ＋1
            h = (h * base + (ord(ch) - ord('0') + 1)) % mod
        return h
    
    # 各ブロックごとに，順方向ハッシュ・逆方向ハッシュ・ブロックの長さを求める
    # S を T 回連結したブロックのハッシュは，
    #   H_block = H(S) * (1 + base^|S| + base^(2|S|) + ... + base^((T-1)|S|))
    # とできる（mod arithmetic）。
    block_data = []  # 各要素: (L, total_len, h1, h2, hr1, hr2) mod mod1, mod2
    for S, T in blocks:
        L = len(S)
        tot = L * T  # ブロック全体の長さ
        # S の順方向ハッシュ
        hS1 = compute_hashes(S, mod1)
        hS2 = compute_hashes(S, mod2)
        # S の逆順ハッシュ（S[::-1]）
        hrS1 = compute_hashes(S[::-1], mod1)
        hrS2 = compute_hashes(S[::-1], mod2)
        # 幾何級数の和の係数： 1 + base^L + base^(2L) + ... + base^((T-1)L)
        r1 = pow(base, L, mod1)
        r2 = pow(base, L, mod2)
        geo1 = geo_sum(r1, T, mod1)
        geo2 = geo_sum(r2, T, mod2)
        # ブロック全体のハッシュ（順方向）
        block_hash1 = (hS1 * geo1) % mod1
        block_hash2 = (hS2 * geo2) % mod2
        # ブロック全体のハッシュ（逆方向）： S[::-1] を T 回連結
        block_rhash1 = (hrS1 * geo1) % mod1
        block_rhash2 = (hrS2 * geo2) % mod2
        
        block_data.append((L, tot, block_hash1, block_hash2, block_rhash1, block_rhash2))
    
    # 全体の文字列 X のハッシュを，順方向・逆方向それぞれ求める。
    total_len = 0  # X の先頭からの長さ（論理的な指数）
    hash1 = 0
    hash2 = 0
    for L, tot, bh1, bh2, _, _ in block_data:
        # 既に構築した文字列の後ろにこのブロックを付ける．
        hash1 = (hash1 + bh1 * pow(base, total_len, mod1)) % mod1
        hash2 = (hash2 + bh2 * pow(base, total_len, mod2)) % mod2
        total_len += tot

    # 逆方向のハッシュ： X[::-1] = (block_K reversed) concat ... concat (block_1 reversed)
    rhash1 = 0
    rhash2 = 0
    offset = 0
    for L, tot, _, _, brh1, brh2 in reversed(block_data):
        rhash1 = (rhash1 + brh1 * pow(base, offset, mod1)) % mod1
        rhash2 = (rhash2 + brh2 * pow(base, offset, mod2)) % mod2
        offset += tot
    
    # X が回文なら，順方向ハッシュと逆方向ハッシュが一致するはず
    if hash1 == rhash1 and hash2 == rhash2:
        sys.stdout.write("Yes")
    else:
        sys.stdout.write("No")

if __name__ == '__main__':
    solve()
0