結果

問題 No.931 Multiplicative Convolution
ユーザー tktk_snsntktk_snsn
提出日時 2021-06-03 20:36:22
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 732 ms / 2,000 ms
コード長 1,551 bytes
コンパイル時間 123 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 69,196 KB
最終ジャッジ日時 2024-11-17 08:24:54
合計ジャッジ時間 15,019 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 494 ms
44,576 KB
testcase_01 AC 504 ms
44,312 KB
testcase_02 AC 513 ms
44,120 KB
testcase_03 AC 510 ms
44,576 KB
testcase_04 AC 524 ms
44,448 KB
testcase_05 AC 501 ms
44,448 KB
testcase_06 AC 493 ms
44,320 KB
testcase_07 AC 578 ms
44,700 KB
testcase_08 AC 732 ms
68,508 KB
testcase_09 AC 700 ms
67,072 KB
testcase_10 AC 708 ms
69,196 KB
testcase_11 AC 696 ms
66,132 KB
testcase_12 AC 628 ms
57,352 KB
testcase_13 AC 721 ms
67,884 KB
testcase_14 AC 728 ms
67,448 KB
testcase_15 AC 718 ms
68,840 KB
testcase_16 AC 720 ms
68,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import numpy as np
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353


def gen(p):
    fact = []
    phi = p - 1
    n = phi
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            fact.append(i)
            while n % i == 0:
                n //= i
    if n > 1:
        fact.append(n)
    for res in range(2, p+1):
        ok = True
        for f in fact:
            if pow(res, phi//f, p) == 1:
                ok = False
                break
        if ok:
            return res
    return -1


def conv(A, B):
    n = len(A) + len(B) - 1
    sz = 1 << (n-1).bit_length()
    res = ifft(fft(A, sz) * fft(B, sz), sz)
    return np.rint(res).astype(np.int64)[:n]


def mod_conv(A, B):
    a1, a2 = np.divmod(A, 1 << 15)
    b1, b2 = np.divmod(B, 1 << 15)
    x = conv(a1, b1) % mod
    y = conv(a2, b2) % mod
    xy = (conv(a1 + a2, b1 + b2) - (x + y)) % mod
    res = (x << 30) % mod + (xy << 15) % mod + y
    return res % mod


def mod_pow(n, power, mod):
    """ [n^0, n^1, n^2, ..., n^(power-1)] """
    D = power.bit_length()
    res = np.empty(1 << D, np.int64)
    res[0] = 1
    for d in range(D):
        res[(1 << d): (1 << (d + 1))] = \
            res[:(1 << d)] * n % mod * res[(1 << d) - 1] % mod
    return res[:power]


P = int(input())
A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)
g = gen(P)
idx = mod_pow(g, P - 1, P) - 1

X = A[idx]
Y = B[idx]
Z = mod_conv(X, Y)

Z[:P-2] += Z[P-1:]

ans = np.empty(P-1, dtype=np.int64)
ans[idx] = Z[:P-1] % mod
print(*ans)
0