結果

問題 No.2994 べき内積
コンテスト
ユーザー むつある
提出日時 2024-12-19 01:25:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,031 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 142,040 KB
最終ジャッジ日時 2024-12-19 01:26:17
合計ジャッジ時間 59,559 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 TLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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}
    """
    N = len(a)
    c = [0]*(N)
    for n in range(N):
        s = 0
        # 畳み込み: a_0*b_n + a_1*b_{n-1} + ... + a_n*b_0
        for m in range(n+1):
            s += a[m]*b[n-m]
            s%=p
        c[n] = s
    return c

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)]
p=1009

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=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) :
            for k in range(K) :
                c[i][j] += a[i][k] * b[k][j]
                c[i][j] %= p
    return c
    
ans=mat_mul(x,b)
for i in ans:
  print(i[0]%p,end=' ')
print()
0