結果

問題 No.3046 White Tiger vs Monster
ユーザー lam6er
提出日時 2025-04-15 22:56:48
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 932 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 67,528 KB
最終ジャッジ日時 2025-04-15 22:58:19
合計ジャッジ時間 7,888 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

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

# Filter x to include only steps <= K and sort them
x = [xi for xi in x if xi <= K]
x.sort()

dp = [0] * (K + 1)
sum_dp = [0] * (K + 1)

dp[0] = 1
sum_dp[0] = 1

for k in range(1, K + 1):
    total = 0
    # Find the rightmost index where x_i <= k using binary search
    left, right = 0, len(x)
    while left < right:
        mid = (left + right) // 2
        if x[mid] <= k:
            left = mid + 1
        else:
            right = mid
    # Iterate through all valid x_i (up to left-1)
    for xi in x[:left]:
        prev = k - xi
        if prev >= 0:
            total += sum_dp[prev]
            if prev - 1 >= 0:
                total -= sum_dp[prev - 1]
            # Ensure the total stays within the modulo bounds
            total %= MOD
    dp[k] = total % MOD
    sum_dp[k] = (sum_dp[k - 1] + dp[k]) % MOD

print(dp[K] % MOD)
0