結果
問題 |
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 |
ソースコード
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()