結果

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

ソースコード

diff # 

MOD = 258280327

def multiply(a, b):
    len_a = len(a)
    len_b = len(b)
    if len_a == 0 or len_b == 0:
        return []
    if len_a < len_b:
        a, b = b, a
        len_a, len_b = len_b, len_a
    if len_b <= 32:
        res = [0] * (len_a + len_b - 1)
        for i in range(len_a):
            ai = a[i]
            if ai == 0:
                continue
            for j in range(len_b):
                if i + j >= len(res):
                    break
                res[i+j] = (res[i+j] + ai * b[j]) % MOD
        return res
    split = (len_a + 1) // 2
    a0 = a[:split]
    a1 = a[split:]
    b0 = b[:min(split, len_b)]
    b1 = b[min(split, len_b):]
    
    z0 = multiply(a0, b0)
    z2 = multiply(a1, b1)
    
    a01 = []
    max_a = max(len(a0), len(a1))
    for i in range(max_a):
        val = 0
        if i < len(a0):
            val += a0[i]
        if i < len(a1):
            val += a1[i]
        a01.append(val % MOD)
    b01 = []
    max_b = max(len(b0), len(b1))
    for i in range(max_b):
        val = 0
        if i < len(b0):
            val += b0[i]
        if i < len(b1):
            val += b1[i]
        b01.append(val % MOD)
    
    z1 = multiply(a01, b01)
    
    z1 = subtract(z1, z0)
    z1 = subtract(z1, z2)
    
    res = [0] * (len_a + len_b - 1)
    for i in range(len(z0)):
        res[i] = (res[i] + z0[i]) % MOD
    for i in range(len(z1)):
        pos = i + split
        if pos < len(res):
            res[pos] = (res[pos] + z1[i]) % MOD
    for i in range(len(z2)):
        pos = i + 2 * split
        if pos < len(res):
            res[pos] = (res[pos] + z2[i]) % MOD
    return res

def subtract(a, b):
    res = a.copy()
    for i in range(len(b)):
        if i < len(res):
            res[i] = (res[i] - b[i]) % MOD
    return res

n = int(input())
F = list(map(int, input().split()))
m = int(input())
G = list(map(int, input().split()))

F = [x % MOD for x in F]
G = [x % MOD for x in G]

product = multiply(F, G)

while len(product) > 1 and product[-1] == 0:
    product.pop()

L = len(product) - 1
print(L)
print(' '.join(map(str, product)) if product else '0')
0