結果

問題 No.2272 多項式乗算 mod 258280327
ユーザー gew1fw
提出日時 2025-06-12 13:00:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,833 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 231,048 KB
最終ジャッジ日時 2025-06-12 13:07:18
合計ジャッジ時間 7,479 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 WA * 3 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 258280327

def main():
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr += 1
    F = list(map(lambda x: int(x) % MOD, input[ptr:ptr + N + 1]))
    ptr += N + 1

    M = int(input[ptr])
    ptr += 1
    G = list(map(lambda x: int(x) % MOD, input[ptr:ptr + M + 1]))
    ptr += M + 1

    def multiply(a, b):
        len_a = len(a)
        len_b = len(b)
        if len_a == 0 or len_b == 0:
            return []
        max_len = max(len_a, len_b)
        if max_len <= 100:
            return naive_multiply(a, b)
        mid = (max_len + 1) // 2

        def split(poly, mid):
            return poly[:mid], poly[mid:]

        a_low, a_high = split(a, mid)
        b_low, b_high = split(b, mid)

        z0 = multiply(a_low, b_low)
        z2 = multiply(a_high, b_high)

        a_low_ext = a_low + [0] * (mid - len(a_low))
        a_high_ext = a_high + [0] * (mid - len(a_high))
        a_mid = [(a_low_ext[i] + a_high_ext[i]) % MOD for i in range(mid)]

        b_low_ext = b_low + [0] * (mid - len(b_low))
        b_high_ext = b_high + [0] * (mid - len(b_high))
        b_mid = [(b_low_ext[i] + b_high_ext[i]) % MOD for i in range(mid)]

        z1 = multiply(a_mid, b_mid)

        z1 = sub_poly(sub_poly(z1, z0), z2)

        result = [0] * (len_a + len_b - 1)
        for i in range(len(z0)):
            result[i] = (result[i] + z0[i]) % MOD
        for i in range(len(z1)):
            if mid + i < len(result):
                result[mid + i] = (result[mid + i] + z1[i]) % MOD
            else:
                result.append(z1[i] % MOD)
        for i in range(len(z2)):
            if 2 * mid + i < len(result):
                result[2 * mid + i] = (result[2 * mid + i] + z2[i]) % MOD
            else:
                result.append(z2[i] % MOD)
        return result

    def naive_multiply(a, b):
        res = [0] * (len(a) + len(b) - 1)
        for i in range(len(a)):
            if a[i] == 0:
                continue
            for j in range(len(b)):
                if b[j] == 0:
                    continue
                res[i + j] = (res[i + j] + a[i] * b[j]) % MOD
        return res

    def sub_poly(a, b):
        len_a = len(a)
        len_b = len(b)
        res = a.copy()
        for i in range(len_b):
            if i < len_a:
                res[i] = (res[i] - b[i]) % MOD
            else:
                res.append((-b[i]) % MOD)
        while len(res) > 0 and res[-1] == 0:
            res.pop()
        return res

    product = multiply(F, G)
    L = len(product) - 1 if product else 0
    while L > 0 and product[L] == 0:
        L -= 1
    product = product[:L + 1] if product else [0]
    print(L)
    if L == 0:
        print(product[0] % MOD)
    else:
        print(' '.join(map(str, product)))

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