結果
問題 |
No.997 Jumping Kangaroo
|
ユーザー |
|
提出日時 | 2022-08-20 12:07:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,206 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 76,836 KB |
最終ジャッジ日時 | 2024-10-09 05:23:37 |
合計ジャッジ時間 | 4,602 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 3 WA * 22 |
ソースコード
# 行列の乗算(mod) def mat_mul(a, b): I, K, J = len(a), len(b), len(b[0]) c = [[0 for j in range(J)] for i in range(I)] for i in range(I): for k in range(K): for j in range(J): c[i][j] += a[i][k] * b[k][j] c[i][j] %= mod return c # 行列の累乗(mod) def mat_pow(a, n): b = [[0 for j in range(len(a))] for i in range(len(a))] for i in range(len(a)): b[i][i] = 1 while n > 0: if n & 1: b = mat_mul(b, a) a = mat_mul(a, a) n >>= 1 return b n,w,K = map(int,input().split()) A = [int(i) for i in input().split()] mod = 10**9+7 a = [[0]*(2*w+1) for i in range(2*w+1)] aa = [[0]*(2*w+1) for i in range(2*w+1)] aa[0][0] = 1 for i in range(2*w): for j in range(i+1): for k in range(n): if i + A[k] <= 2*w: aa[i][i+A[k]] += aa[j][i] aa[i][i+A[k]] %= mod else: break #print(aa) #exit() gr = mat_pow(aa,(K+1)//2) ans = 0 if k % 2 == 1: for i in range(w+1): ans += gr[i][w] ans %= mod else: for i in range(2*w+1): ans += gr[i][2*w] ans %= mod print(ans)