結果

問題 No.2994 べき内積
コンテスト
ユーザー LyricalMaestro
提出日時 2026-06-13 04:56:16
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,048 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 641 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 141,952 KB
最終ジャッジ日時 2026-06-13 04:56:28
合計ジャッジ時間 5,709 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/2994

p = 1009

def prod(poly1, poly2):
    n = len(poly1)
    new_poly = [0] * n
    for i in range(n):
        x = 0
        for j in range(i + 1):
            x += (poly1[j] * poly2[i - j]) % p
            x %= p
        new_poly[i] = x
    return new_poly




def main():
    M, N = map(int, input().split())
    K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    # 多項式　f^p = A[0]であることから...

    k = 0
    for i in reversed(range(1, M + 1)):
        k += K[i]
    if A[0] > 0:
        coef = pow(A[0], k, p)
    else:
        coef = 1

    k0 = K[0]
    poly = [0] * (N + 1)
    poly[0] = 1
    base_poly = A.copy()
    while k0 > 0:
        if k0 % 2 == 1:
            poly = prod(poly, base_poly)

        base_poly = prod(base_poly, base_poly)
        k0 //= 2

    answers = []
    for i in range(N + 1):
        ans = (coef * poly[i]) % p
        answers.append(ans)
    print(" ".join(map(str,answers)))










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