結果

問題 No.766 金魚すくい
ユーザー qwewe
提出日時 2025-05-14 13:15:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,808 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 268,208 KB
最終ジャッジ日時 2025-05-14 13:17:14
合計ジャッジ時間 7,308 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set higher recursion depth for safety, although this DP is iterative
# sys.setrecursionlimit(2000) 

# Use fast I/O
input = sys.stdin.readline

def solve():
    # Read input N: number of goldfish, M: number of poi, P: probability percent of breaking
    N, M, P_percent = map(int, input().split())
    # Read goldfish values
    V = list(map(int, input().split()))

    # Define modulus
    MOD = 10**9 + 7

    # Handle edge case P=0:
    # If P=0, probability of breaking is 0. Poi never breaks.
    # We can scoop all N goldfish as long as we have at least one poi (M >= 1 constraint is given).
    # The stopping condition "all M poi break" is never met.
    # The process stops when "all N goldfish are scooped".
    # The total expected value is simply the sum of all goldfish values.
    if P_percent == 0:
        total_value = 0
        for x in V:
            total_value = (total_value + x) % MOD
        print(total_value)
        return

    # Handle edge case P=100:
    # If P=100, probability of breaking is 100%. Any attempt breaks the poi.
    # We never succeed in scooping any fish.
    # The total expected value is 0.
    if P_percent == 100:
        print(0)
        return

    # Calculate modular inverse of 100 to compute probabilities p and q
    # Using Fermat's Little Theorem: a^(MOD-2) mod MOD is the inverse of a mod MOD for prime MOD.
    inv100 = pow(100, MOD - 2, MOD)
    
    # Calculate probability p (poi breaks) and q (scoop succeeds)
    p = (P_percent * inv100) % MOD
    # Calculate q = 1 - p. Add MOD to handle potential negative result before taking modulo.
    q = (1 - p + MOD) % MOD 

    # Sort goldfish values in descending order. The optimal strategy is greedy:
    # always attempt to scoop the available goldfish with the highest value.
    V.sort(reverse=True) 

    # Initialize DP state array.
    # E_next[l] will store the expected value E(i+1, l), which means:
    # we have considered fish 1 to i, and l poi have broken. We are about to consider fish i+1.
    # Initially, represents E(N+1, l) = 0 for all l, as there are no more fish after N.
    E_next = [0] * (M + 1) 

    # Precompute powers of p modulo MOD, needed for DP calculation.
    # p_powers[k] = p^k mod MOD
    p_powers = [1] * (M + 1)
    for k in range(1, M + 1):
        p_powers[k] = (p_powers[k-1] * p) % MOD

    # DP calculation main loop
    # We iterate backwards from the last fish (index N-1) down to the first fish (index 0).
    # This corresponds to calculating E(i, l) based on values E(i+1, *).
    
    # E_curr[l] stores E(i, l) for the current fish i.
    E_curr = [0] * (M + 1) 
    # S_curr[l] is a helper array to compute the summation term efficiently.
    # S(i, l) = sum_{j=0}^{M-l-1} p^j * E(i+1, l+j)
    S_curr = [0] * (M + 1) 

    # Loop through fish i from N down to 1 (0-indexed: N-1 down to 0)
    for i in range(N - 1, -1, -1): 
        # Get the value of the current fish being considered
        Vi = V[i] 
        
        # Compute helper array S_curr for current fish i, using E_next which holds values for E(i+1, *)
        # The recurrence relation for S is S(i, l) = E(i+1, l) + p * S(i, l+1).
        # We compute this backwards from l = M-1 down to 0.
        
        # Base case for the recurrence S(i, M) = 0
        S_curr[M] = 0 
        for l in range(M - 1, -1, -1):
            # Calculate S_curr[l] using the value E_next[l] = E(i+1, l) and the previously computed S_curr[l+1].
            S_curr[l] = (E_next[l] + p * S_curr[l+1]) % MOD
        
        # Compute E_curr[l] = E(i, l) using the formula:
        # E(i, l) = Vi * (1 - p^{M-l}) + q * S(i, l)
        # Iterate l from 0 to M-1.
        for l in range(M):
            # Calculate (1 - p^{M-l}) mod MOD safely. Add MOD before taking modulo to handle potential negative result.
            one_minus_p_pow = (1 - p_powers[M-l] + MOD) % MOD 
            # Calculate the first term: Vi * (1 - p^{M-l})
            term1 = (Vi * one_minus_p_pow) % MOD
            # Calculate the second term: q * S(i, l)
            term2 = (q * S_curr[l]) % MOD
            # Combine the two terms
            E_curr[l] = (term1 + term2) % MOD
        
        # Base case for E: E(i, M) = 0 because if M poi are broken, we cannot scoop anymore.
        E_curr[M] = 0 

        # Prepare E_next for the next iteration (which will consider fish i-1).
        # E_next should hold the values E(i, l) that we just computed in E_curr.
        # Using list slicing `[:]` creates a copy of E_curr. This is important.
        E_next = E_curr[:] 

    # After the loop finishes, E_next holds the values E(1, l).
    # The final answer is E(1, 0), the expected value starting with fish 1 and 0 broken poi.
    print(E_next[0]) 

# Call the solve function to run the program
solve()
0