結果

問題 No.3046 White Tiger vs Monster
ユーザー lam6er
提出日時 2025-03-31 17:23:46
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 598 bytes
コンパイル時間 375 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 65,792 KB
最終ジャッジ日時 2025-03-31 17:24:38
合計ジャッジ時間 12,830 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 10**9 + 7

K = int(input())
N = int(input())
x = list(map(int, input().split()))

# Find valid step sizes up to K
idx = bisect.bisect_right(x, K)
valid_x = x[:idx]
m = len(valid_x)

if m == 0:
    print(0)
    exit()

dp = [0] * (K + 1)
dp[0] = 1  # Base case: one way to be at step 0

for i in range(1, K + 1):
    # Find the number of valid steps that are <= i
    j_max = bisect.bisect_right(valid_x, i)
    total = 0
    for j in range(j_max):
        total += dp[i - valid_x[j]]
        if total >= MOD:
            total -= MOD
    dp[i] = total % MOD

print(dp[K] % MOD)
0