結果

問題 No.2272 多項式乗算 mod 258280327
ユーザー gew1fw
提出日時 2025-06-12 20:21:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,936 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 137,580 KB
最終ジャッジ日時 2025-06-12 20:21:44
合計ジャッジ時間 10,557 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 2 TLE * 2 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

MOD = 258280327

def add_polynomials(a, b):
    max_len = max(len(a), len(b))
    res = [0] * max_len
    for i in range(max_len):
        if i < len(a):
            res[i] = (res[i] + a[i]) % MOD
        if i < len(b):
            res[i] = (res[i] + b[i]) % MOD
    return res

def subtract_polynomials(a, b):
    max_len = max(len(a), len(b))
    res = [0] * max_len
    for i in range(max_len):
        val = 0
        if i < len(a):
            val = (val + a[i]) % MOD
        if i < len(b):
            val = (val - b[i]) % MOD
        res[i] = val % MOD
    return res

def multiply_polynomials(f, g):
    if len(f) == 0 or len(g) == 0:
        return []
    max_len = max(len(f), len(g))
    f_padded = f + [0] * (max_len - len(f))
    g_padded = g + [0] * (max_len - len(g))
    if max_len == 1:
        return [(f_padded[0] * g_padded[0]) % MOD]
    mid = max_len // 2
    f_low = f_padded[:mid]
    f_high = f_padded[mid:]
    g_low = g_padded[:mid]
    g_high = g_padded[mid:]
    a = multiply_polynomials(f_low, g_low)
    b = multiply_polynomials(f_high, g_high)
    f_sum = add_polynomials(f_low, f_high)
    g_sum = add_polynomials(g_low, g_high)
    c = multiply_polynomials(f_sum, g_sum)
    middle = subtract_polynomials(c, a)
    middle = subtract_polynomials(middle, b)
    middle_shifted = [0] * mid + middle
    b_shifted = [0] * (2 * mid) + b
    res = add_polynomials(a, middle_shifted)
    res = add_polynomials(res, b_shifted)
    return res

def main():
    n = int(stdin.readline())
    f = list(map(int, stdin.readline().split()))
    m = int(stdin.readline())
    g = list(map(int, stdin.readline().split()))
    h = multiply_polynomials(f, g)
    l = n + m
    if l < 0:
        l = 0
    h = h[:l + 1]
    if all(c == 0 for c in h):
        print(0)
        print(0)
    else:
        print(l)
        print(' '.join(map(str, h)))

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