結果

問題 No.2994 べき内積
コンテスト
ユーザー むつある
提出日時 2024-12-19 02:02:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,613 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 276,384 KB
最終ジャッジ日時 2024-12-19 02:03:58
合計ジャッジ時間 62,409 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

p=1009

# ---- FFT関連開始 ----
import math

def fft(a, inv=False):
    # Cooley-Tukey FFT
    # a: 複素数列（lenは2冪）
    # inv=Trueで逆変換
    n = len(a)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j |= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        angle = 2*math.pi/length * (-1 if inv else 1)
        wlen = complex(math.cos(angle), math.sin(angle))
        for i in range(0, n, length):
            w = 1+0j
            for j in range(i, i+(length>>1)):
                u = a[j]
                v = a[j+(length>>1)]*w
                a[j] = u+v
                a[j+(length>>1)] = u-v
                w *= wlen
        length <<= 1
    if inv:
        # 逆変換時は1/n倍
        invn = 1.0/n
        for i in range(n):
            a[i] *= invn

def poly_mul(A, B):
    # A, Bをmod pで畳み込み
    # FFTを用いて(O(N log N))で計算する
    # A, Bは長さN程度、結果は長さ最大2N-1
    length = len(A) + len(B) - 1
    n = 1
    while n < length:
        n <<= 1
    fA = [0]*(n)
    fB = [0]*(n)
    for i in range(len(A)):
        fA[i] = A[i]
    for i in range(len(B)):
        fB[i] = B[i]

    fA = [complex(x,0) for x in fA]
    fB = [complex(x,0) for x in fB]

    fft(fA, inv=False)
    fft(fB, inv=False)
    for i in range(n):
        fA[i] = fA[i]*fB[i]
    fft(fA, inv=True)

    # 実部を整数に丸めてmod p
    C = [round(fA[i].real)%p for i in range(length)]
    return C
# ---- FFT関連終了 ----

def toeplitz_multiply(a, b):
    """
    下三角トープリッツ行列 A, B (N×N) が第一列 a, b で与えられるとき、
    C = A*B も下三角トープリッツ行列で、その第一列 c を返す。
    c_n = sum_{m=0}^n a_m * b_{n-m}

    a,bは長さNのリスト
    これは多項式a(x)=a0+a1x+...とb(x)=b0+b1x+...の
    畳み込み(a*b)の先頭N項と一致。
    """
    c_full = poly_mul(a, b)
    return c_full[:len(a)]

def toeplitz_identity(N):
    """
    N×Nの下三角トープリッツ形式の単位行列の第一列は [1,0,0,...,0]
    """
    a = [0]*N
    a[0] = 1
    return a

def toeplitz_power(a, K):
    """
    下三角トープリッツ行列 A (第一列 a) の K乗 A^K を求める。
    二分累乗法利用。
    """
    N = len(a)
    result = toeplitz_identity(N)
    base = a[:]

    k = K
    while k > 0:
        if k & 1:
            result = toeplitz_multiply(result, base)
        base = toeplitz_multiply(base, base)
        k >>= 1
    
    return result

M,N=map(int,input().split())
M+=1
N+=1
k=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[[a[i]] for i in range(N)]

for i in range(M):
    if k[i]!=0:
        x=i
        k[x]-=1
        break
    for j in range(x):
        k[j]=p-1

keep=[toeplitz_identity(N)]

for i in range(M):
    keep.append(toeplitz_power(a, k[i]))
    # a を p回累乗した結果で更新
    a = toeplitz_power(a, p)

now=keep[0][:]
for i in range(1,M+1):
    now=toeplitz_multiply(now, keep[i])

x=[[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i+1):
        x[i][j]=now[i-j]

def mat_mul(a, b):
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0]*J for _ in range(I)]
    for i in range(I):
        for j in range(J):
            s=0
            for kk in range(K):
                s += a[i][kk]*b[kk][j]
            c[i][j]=s%p
    return c

ans=mat_mul(x,b)
for i in ans:
    print(i[0]%p, end=' ')
print()
0