educational codeforces 159

最近、コドフォに復帰しつつある。
エデュフォはpython のメモリエラーに苦しめられて散々だった。
A:全部1の時以外できる。

B:文章が長い

C:ソートしてan-1-anのgcd、an+1=an-k*gcdでできるだけ大きく取る。

E: トライ木でやるとメモリエラーに。versionをpypy3 64bitからpypy3に帰ると少し改善するがだめ
ロリハでやるとTLEするかmod小さすぎて衝突するかを繰り返す。ロリハでググってきて

ABC331F Palindrome Query
Rolling Hash + 平方分割でギリギリAC！
mod = 2^61-1 のロリハ演算が本当に速い、PythonのO(Q√N)解を通してくれるとは思いませんでしたhttps://t.co/dISv4v4t9y

実装にあたり、keymoonさんの記事を参考にしました
ありがとうございました！https://t.co/QNV1ojL9UG

— ネイヴル (@navel_tos) 2023年12月3日

などのようにするがTLE。
pypy3 64bitに戻してコンテスト後AC

import sys;input=sys.stdin.readline
from collections import defaultdict
D = defaultdict(int)
N, = map(int, input().split())
X = list()
#MOD = 228216557729
MOD = 2**61-1

def mul(a,b):  #a*b MOD 2^61-1 を高速に求める
    mask30, mask31, MOD = (1<<30)-1, (1<<31)-1, (1<<61)-1
    p,d = a>>31, a & mask31  #a = p*mask31+d
    q,e = b>>31, b & mask31  #b = q*mask31+e
    m = p*e + q*d
    x,y = m>>30, m & mask30
    ans = p*q*2 + x + (y<<31) + d*e
    if 0 <= ans < MOD: return ans
    elif MOD <= ans:
        r,s = ans>>61, ans & MOD
        return r+s if r+s<MOD else r+s-MOD
    else: return ans % MOD


r = 27
for _ in range(N):
    X.append([ord(c)-97 for c in input().strip()])
R = 0
for x in X:
    R += 2*N*len(x)
    hsh = 0
    kk = 1
    for i in range(len(x)):
        c = x[i]
        hsh += mul((c+1),kk)
        hsh %= MOD
        kk = mul(kk,r)%MOD
        D[hsh] += 1
for x in X:
    idx = 1
    hsh = 0
    kk = 1
    for i in range(len(x)-1,-1,-1):
        c = x[i]
        hsh += mul((c+1),kk)
        hsh %= MOD
        kk = mul(kk,r)%MOD
        R -= 2*D[hsh]
        idx += 1
print(R)