結果

問題 No.2199 lower_bound and upper_bound
ユーザー qwewe
提出日時 2025-05-14 13:22:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,132 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 76,208 KB
最終ジャッジ日時 2025-05-14 13:24:23
合計ジャッジ時間 4,610 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

N, L, U = map(int, input().split())

# dp[s] stores the number of sequences B_1, ..., B_k (current length k)
# such that sum(B_1, ..., B_k) = s
# and sum(B_1, ..., B_j) <= U+j for j <= k.
# B_j >= 0.

# Initial state: k=0 (empty sequence of B)
# dp[0] = 1 (sum is 0, 1 way - empty sequence)
# Max sum for S_N is U+N. Array size U+N+1.
dp = [0] * (U + N + 1)
if 0 <= U + N : # Check if dp array has non-negative size; U+N can be 0 if U=0,N=0 (not allowed by constraints)
                # Or if U+N is very small. Max sum U+N is at least 0.
    dp[0] = 1

# Iterate for k from 1 to N (length of sequence B_1, ..., B_k)
for k_idx in range(1, N + 1):
    new_dp = [0] * (U + N + 1)
    current_prefix_sum = 0
    
    # Max sum for S_{k-1} was U + (k-1)
    limit_prev_sum_idx = U + (k_idx - 1)
    
    # Max sum for S_k is U + k
    limit_curr_sum_idx = U + k_idx

    for s_curr in range(limit_curr_sum_idx + 1):
        # new_dp[s_curr] = sum_{j=0 to min(s_curr, limit_prev_sum_idx)} dp[j]
        
        if s_curr <= limit_prev_sum_idx:
            # current_prefix_sum accumulates dp[0]...dp[s_curr]
            # We need to ensure s_curr is a valid index for dp array,
            # which it is, as dp is sized U+N+1 and s_curr <= U+k_idx <= U+N.
            current_prefix_sum = (current_prefix_sum + dp[s_curr]) % MOD
            new_dp[s_curr] = current_prefix_sum
        else: 
            # s_curr > limit_prev_sum_idx
            # The sum is capped: sum_{j=0 to limit_prev_sum_idx} dp[j].
            # This value is what current_prefix_sum held after processing s_curr = limit_prev_sum_idx.
            new_dp[s_curr] = current_prefix_sum
            
    dp = new_dp

# Final result: sum dp[s] for s from (L+N) to (U+N)
ans = 0
# The sum s must be >= L+N.
# Also, s cannot exceed U+N (max possible sum).
# And s must be a valid index for dp array.
# dp array is size U+N+1, so max index is U+N.
start_sum = L + N
end_sum = U + N

for s in range(start_sum, end_sum + 1):
    if 0 <= s < len(dp): # Check bounds: s must be non-negative and within dp array
        ans = (ans + dp[s]) % MOD

print(ans)
0