結果

問題 No.1388 Less than K
ユーザー lam6er
提出日時 2025-04-09 21:02:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,575 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 93,028 KB
最終ジャッジ日時 2025-04-09 21:04:16
合計ジャッジ時間 16,157 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    H, W, K = map(int, sys.stdin.readline().split())
    T = H + W - 2
    m = K // 2
    X_max = min(H-1, W-1)

    # Precompute factorial and inverse factorial
    max_n = 2 * (H + W)
    fact = [1] * (max_n + 1)
    inv_fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    def comb(n, k):
        if n < 0 or k < 0 or k > n:
            return 0
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

    ans = 0
    for X in range(X_max + 1):
        Z0 = W-1 - X
        Z1 = H-1 - X
        if Z0 < 0 or Z1 < 0:
            continue

        steps_comb = comb(T, 2 * X)
        split_comb = comb(T - 2 * X, Z0)
        if steps_comb == 0 or split_comb == 0:
            continue

        # Compute D(X)
        D = 0
        m_plus_1 = m + 1
        if m_plus_1 == 0:
            m_plus_1 = 1  # to avoid division by zero, but m=0 implies K=0 handled in loop
        k_min = - (X // m_plus_1)
        k_max = X // m_plus_1

        for k in range(k_min, k_max + 1):
            x_prime = X - k * m_plus_1
            binom = comb(2 * X, x_prime)
            sign = -1 if k % 2 else 1
            if binom != 0:
                D = (D + sign * binom) % MOD

        term = steps_comb * split_comb % MOD
        term = term * D % MOD
        ans = (ans + term) % MOD

    print(ans % MOD)

if __name__ == '__main__':
    main()
0