結果

問題 No.2457 Stampaholic (Easy)
ユーザー lam6er
提出日時 2025-03-26 15:54:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 394 ms / 4,000 ms
コード長 1,818 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 110,448 KB
最終ジャッジ日時 2025-03-26 15:54:52
合計ジャッジ時間 4,515 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
from collections import defaultdict
MOD = 998244353
def get_distribution(H, K):
    dist = defaultdict(int)
    s = H - K + 1
    # Case 1: l <= K-1
    if s >= K - 1:
        for a in range(1, K):
            dist[a] += 1
    else:
        for a in range(1, s + 1):
            dist[a] += 1
        remaining = (K - 1) - s
        if remaining > 0:
            dist[s] += remaining
    # Case 2a: a = K
    t = max(0, H - 2 * K + 2)
    if t > 0:
        dist[K] += t
    # Case 2b: a_val from 1 to len_case2b
    start = max(K, H - K + 2)
    end = H
    if start <= end:
        len_case2b = end - start + 1
        for a in range(1, len_case2b + 1):
            dist[a] += 1
    return dist
def main():
    H, W, N, K = map(int, sys.stdin.readline().split())
    # Compute row distribution
    row_dist = get_distribution(H, K)
    # Compute column distribution
    col_dist = get_distribution(W, K)
    # Compute T and inv_T
    Th = (H - K + 1) % MOD
    Tw = (W - K + 1) % MOD
    T = (Th * Tw) % MOD
    if T == 0:
        print(0)
        return
    inv_T = pow(T, MOD - 2, MOD)
    # Calculate the total expectation
    total = 0
    # Precompute pow for each unique c_val
    pow_cache = {}
    for a_val, a_cnt in row_dist.items():
        for b_val, b_cnt in col_dist.items():
            c_val = a_val * b_val
            numerator = (c_val % MOD) * inv_T % MOD
            prob_not = (1 - numerator) % MOD
            if prob_not in pow_cache:
                pow_val = pow_cache[prob_not]
            else:
                pow_val = pow(prob_not, N, MOD)
                pow_cache[prob_not] = pow_val
            term = (1 - pow_val) % MOD
            cnt = (a_cnt * b_cnt) % MOD
            total = (total + term * cnt) % MOD
    print(total % MOD)
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0