結果

問題 No.2932 えっえっ嘘嘘嘘待って待って待って？？？えマジで？ほんとに？マジでやばすぎなんだけど？えっおっほんとにこんなにDPしちゃっていいんですかい？？？マジでやばすぎなんだけど？？？
ユーザー detteiuu
提出日時 2025-10-06 22:32:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 1,275 bytes
コンパイル時間 558 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 64,416 KB
最終ジャッジ日時 2025-10-06 22:32:24
合計ジャッジ時間 2,544 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

class CP:
    def __init__(self, N):
        self.fact = [1]*(N+1)
        self.fact_inv = [1]*(N+1)
        for i in range(2, N+1):
            self.fact[i] = self.fact[i-1]*i%MOD
        self.fact_inv[N] = pow(self.fact[N], -1, MOD)
        for i in reversed(range(1, N)):
            self.fact_inv[i] = self.fact_inv[i+1]*(i+1)%MOD
    def C(self, N, K):
        if N < 0 or K < 0 or N < K:
            return 0
        return self.fact[N]*self.fact_inv[K]%MOD*self.fact_inv[N-K]%MOD
    def P(self, N, K):
        if N < 0 or K < 0 or N < K:
            return 0
        return self.fact[N]*self.fact_inv[N-K]%MOD
    def H(self, N, K):
        if N < 0 or K < 0:
            return 0
        if N == K == 0: return 1
        return self.C(N+K-1, K)

def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

def C(N, K):
    if N < K:
        return 0
    if N < K*2:
        K = N-K
    top = 1
    for i in range(N, N-K, -1):
        top *= i
        top %= MOD
    bottom = 1
    for i in range(1, K+1):
        bottom *= i
        bottom %= MOD
    return inverse(top, bottom)

MOD = 998244353

H, W, M = map(int, input().split())

if M < H+W-1:
    exit(print(0))

cp = CP(10**5)
print(cp.C(H+W-2, H-1)*C(H+W-1+(M-(H+W-1)), M-(H+W-1))%MOD*pow(M, H*W-H-W+1, MOD)%MOD)
0