結果

問題 No.997 Jumping Kangaroo
コンテスト
ユーザー lam6er
提出日時 2025-03-26 16:00:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 1,435 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 61,444 KB
最終ジャッジ日時 2025-03-26 16:01:06
合計ジャッジ時間 2,682 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, W, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

# Compute a (ways to reach W with sum W)
target_a = W
dp_a = [0] * (target_a + 1)
dp_a[0] = 1
for s in range(target_a + 1):
    for a_j in A:
        next_s = s + a_j
        if next_s > target_a:
            continue
        dp_a[next_s] = (dp_a[next_s] + dp_a[s]) % MOD
a = dp_a[target_a]

# Compute b (ways to reach 2W without hitting W)
target_b = 2 * W
dp_b = [0] * (target_b + 1)
dp_b[0] = 1
for s in range(target_b + 1):
    for a_j in A:
        next_s = s + a_j
        if next_s > target_b or next_s == W:
            continue
        dp_b[next_s] = (dp_b[next_s] + dp_b[s]) % MOD
b = dp_b[target_b]

def multiply(m1, m2):
    a = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD
    b = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD
    c = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD
    d = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD
    return [[a, b], [c, d]]

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

if K == 0:
    print(1 % MOD)
elif K == 1:
    print(a % MOD)
else:
    matrix = [[a, b], [1, 0]]
    powered = matrix_power(matrix, K - 1)
    ans = (powered[0][0] * a + powered[0][1] * 1) % MOD
    print(ans)
0