結果

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

ソースコード

diff # 

class factorial():
    def __init__(self,n=0,mod=998244353):
        self.mod=mod
        self.fact_n=[1]
        self.fact_i=[1]
        self.fact_l=0
        self.create(n)
    
    def create(self,n):
        if self.fact_l<n:
            for i in range(self.fact_l+1,n+1):
                self.fact_n.append((self.fact_n[-1]*i)%self.mod)
                self.fact_i.append(0)
            self.fact_i[n]=pow(self.fact_n[n],self.mod-2,self.mod)
            for i in range(n,self.fact_l+1,-1):
                self.fact_i[i-1]=(self.fact_i[i]*i)%self.mod
            self.fact_l=n
        
    def fact(self,n):
        assert n>=0
        if n>self.fact_l:
            self.create(n)
        return self.fact_n[n]
    
    def fact_inv(self,n):
        assert n>=0
        if n>self.fact_l:
            self.create(n)
        return self.fact_i[n]

    def perm(self,n,r):
        if r<0:
            return 0
        if n>=0:
            if n<r:
                return 0
            return (self.fact(n)*self.fact_inv(n-r))%self.mod
        elif n<0:
            ret=(self.fact(-n+r-1)*self.fact_inv(-n-1))%self.mod
            if r%2==1:
                ret=-ret
                ret%=self.mod
            return ret
    
    def comb(self,n,r):
        if r<0:
            return 0
        if n>=0:
            if n<r:
                return 0
            return (self.fact(n)*self.fact_inv(n-r)*self.fact_inv(r))%self.mod
        elif n<0:
            ret=(self.fact(-n+r-1)*self.fact_inv(-n-1)*self.fact_inv(r))%self.mod
            if r%2==1:
                ret=-ret
                ret%=self.mod
            return ret
    

H,W,M=map(int,input().split())
Mod=998244353
f=factorial(H+W+10,Mod)
r=f.comb(H+W-2,H-1)
g=pow(M,H*W-H-W+1,Mod)

t=1
for i in range(H+W-1):
    t*=M-i
    t%=Mod

t*=f.fact_inv(H+W-1)
t%=Mod
print(r*g*t%Mod)
0