結果

問題 No.3153 probability max K
ユーザー navel_tos
提出日時 2025-05-21 04:10:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,071 ms / 2,000 ms
コード長 1,065 bytes
コンパイル時間 534 ms
コンパイル使用メモリ 81,948 KB
実行使用メモリ 102,468 KB
最終ジャッジ日時 2025-05-21 04:10:36
合計ジャッジ時間 21,572 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 3153 probability max K

#入力受取
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
assert 1 <= N <= 2 * 10 ** 5
assert 1 <= K < MOD
assert all(1 <= Ai < MOD for Ai in A)

#1. DP
def solve_DP(N, K, A):
    #DP[i][f]: i個目のダイスを振る前であって、出目最大がf = 0/1: K未満/ちょうどK
    DP = [1, 0]
    nDP = [0, 0]
    for Ai in A:
        nDP[0] = DP[0] * ( min(Ai, K - 1) * pow(Ai, -1, MOD) % MOD ) % MOD
        nDP[1] = DP[1] * ( min(Ai, K    ) * pow(Ai, -1, MOD) % MOD ) % MOD
        if Ai >= K:
            nDP[1] += DP[0] * pow(Ai, -1, MOD) % MOD
            nDP[1] %= MOD
        DP, nDP = nDP, DP
    return DP[1]


#2. 確率差分
def solve_2(N, K, A):
    def calc(N, X, A):  #すべての出目がX以下となる確率
        ans = 1
        for Ai in A:
            ans = ans * ( min(X, Ai) * pow(Ai, -1, MOD) % MOD ) % MOD
        return ans
    return ( calc(N, K, A) - calc(N, K - 1, A) ) % MOD

assert solve_DP(N, K, A) == solve_2(N, K, A)
print( solve_DP(N, K, A) )
0