結果
問題 |
No.2754 Cumulate and Drop
|
ユーザー |
![]() |
提出日時 | 2024-05-10 22:50:00 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 830 bytes |
コンパイル時間 | 266 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 849,064 KB |
最終ジャッジ日時 | 2024-12-20 06:50:50 |
合計ジャッジ時間 | 18,823 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 MLE * 12 |
ソースコード
''' 行列累乗ライブラリ 使用上の注意→ベクトルを入れる場合も二次元配列にする。 ''' def mat_mul(a, b, m) : 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] %= m return c def mat_pow(x, n, m): y = [[0] * len(x) for _ in range(len(x))] for i in range(len(x)): y[i][i] = 1 while n > 0: if n & 1: y = mat_mul(x, y, m) x = mat_mul(x, x, m) n >>= 1 return y N=int(input()) A=list(map(int,input().split())) A=[A] B=[] B.append([1]*N) for i in range(1,N): B.append([0]*(i-1)+[1]*(N-i+1)) p=998244353 pow=mat_pow(B,N-1,p) print(mat_mul(A,pow,p)[0][0])