結果
問題 |
No.997 Jumping Kangaroo
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:01:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,261 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 61,504 KB |
最終ジャッジ日時 | 2025-04-09 21:01:56 |
合計ジャッジ時間 | 2,147 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
mod = 10**9 + 7 def compute_f1(W, A): target = W dp = [0] * (target + 1) dp[0] = 1 for x in range(1, target + 1): for a in A: if x - a >= 0: dp[x] = (dp[x] + dp[x - a]) % mod return dp[target] def compute_f2(W, A): target = 2 * W dp = [0] * (target + 1) dp[0] = 1 for x in range(1, target + 1): if x == W: dp[x] = 0 continue for a in A: prev = x - a if prev >= 0 and prev != W: dp[x] = (dp[x] + dp[prev]) % mod return dp[target] def multiply(a, b): res = [[0] * 2 for _ in range(2)] for i in range(2): for j in range(2): for k in range(2): res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod return res def matrix_power(mat, power): result = [[1, 0], [0, 1]] # Identity matrix while power > 0: if power % 2 == 1: result = multiply(result, mat) mat = multiply(mat, mat) power //= 2 return result n, w, k = map(int, input().split()) a = list(map(int, input().split())) f1 = compute_f1(w, a) f2 = compute_f2(w, a) T = [ [f1, f2], [1, 0] ] mat = matrix_power(T, k) ans = mat[0][0] % mod print(ans)