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