結果

問題 No.8105 Міжнародний підрядок саміт
コンテスト
ユーザー wasd314
提出日時 2026-08-20 13:43:50
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
MLE  
実行時間 -
コード長 2,221 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 229 ms
コンパイル使用メモリ 96,104 KB
実行使用メモリ 425,484 KB
最終ジャッジ日時 2026-08-20 13:44:01
合計ジャッジ時間 6,404 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1
other MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from functools import cache

oo = 10**18


@cache
def build(n: int):
    n2 = 1 << n
    mid = n * (n + 1) // 2
    nn = n + 1
    mid2 = mid * 2 + 1
    available = [0] * (n2 * nn)
    available[0] = 1 << mid
    le = [oo] * (nn * n2 * mid2)
    ge = [oo] * (nn * n2 * mid2)
    ppc = [0] * n2
    for i in range(n):
        for sub in range(1 << i):
            bit = 1 << i | sub
            ppc[bit] = ppc[sub] + 1
            for p in range(ppc[bit]):
                available[bit * nn + p + 1] |= available[sub * nn + p] << i
                available[bit * nn + p] |= available[sub * nn + p] >> i
    for bit in range(1 << n):
        if bit == 0:
            continue
        for p in range(ppc[bit] + 1):
            av = available[bit * nn + p]
            i0 = (bit * nn + p) * mid2
            if av >> mid - mid & 1:
                le[i0 - mid] = -mid
            for i in range(-mid + 1, mid + 1):
                le[i0 + i] = i if av >> mid + i & 1 else le[i0 + i - 1]
            if av >> mid + mid & 1:
                ge[i0 + mid] = mid
            for i in range(-mid, mid)[::-1]:
                ge[i0 + i] = i if av >> mid + i & 1 else ge[i0 + i + 1]
    return ppc, le, ge


def solve(a, mod):
    n = len(a)
    if n == 1:
        return 0
    if a[1] < a[0]:
        a = a[::-1]
    a0, d = a[0], a[1] - a[0]
    if d == 0:
        return a0 * pow(2, n - 1, mod) % mod
    ppc, le, ge = build(n)
    ans = 0
    mid = n * (n + 1) // 2
    mid2 = mid * 2 + 1
    nn = n + 1
    for bit, bc in enumerate(ppc):
        if bit == 0:
            continue
        ansi = oo
        for p in range(bc + 1):
            ca = 2 * p - bc
            x0 = -ca * a0 // d
            i0 = (bit * nn + p) * mid2
            xl = le[i0 + max(x0, -mid)]
            xr = ge[i0 + min(x0 + 1, mid)]
            sl = abs(ca * a0 + xl * d)
            sr = abs(ca * a0 + xr * d)
            ansi = min(ansi, sl, sr)
        ans += ansi
    return ans % mod


build(13)

if __name__ == "__main__":
    case_t = 1
    case_t = int(input())
    for _ in [None] * case_t:
        n, mod = map(lambda s_: int(s_), input().split())
        a = tuple(map(lambda s_: int(s_), input().split()))
        print(solve(a, mod))
0