結果

問題 No.2529 Treasure Hunter
ユーザー navel_tos
提出日時 2023-11-04 14:35:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 360 ms / 2,000 ms
コード長 2,603 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 112,608 KB
最終ジャッジ日時 2024-09-25 22:03:15
合計ジャッジ時間 8,110 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder411E

#包除かな。各マスに高々1個の宝を埋める(しかも行には高々2個)方法は数え上げ可能。
#このうち、宝のマスが隣り合わない場合の数 を高速に数え上げればよい。
#左端に埋めた場合、右端に埋めた場合、どちらでもない場合 に分ければよいか。
#MODnCr計算機(行数削減版)
class MODnCr:
    def __init__(self,fact_N,MOD,invN=1000):
        self._N=fact_N; self._invN=invN; self._MOD=MOD; self._fact=[1]*(self._N+1); self._inv=[1]*(self._invN+1); self._finv=[1]*(self._N+1)
        for i in range(2,self._N+1): self._fact[i]=self._fact[i-1]*i%self._MOD
        for i in range(2,self._invN+1): self._inv[i]=-self._inv[self._MOD%i]*(self._MOD//i)%self._MOD
        for i in range(2,min(self._invN,self._N)+1): self._finv[i]=self._finv[i-1]*self._inv[i]%self._MOD
        self._finv[self._N]=pow(self._fact[self._N],self._MOD-2,self._MOD)
        for i in range(self._N-1,self._invN,-1): self._finv[i]=self._finv[i+1]*(i+1)%self._MOD
    def _update(self,N):
        if N<=self._N: return 0
        dist=N-self._N; self._fact.extend([1]*dist); self._finv.extend([1]*dist)
        for i in range(self._N+1,N+1): self._fact[i]=self._fact[i-1]*i%self._MOD
        self._finv[N]=self.modinv(self._fact[N])
        for i in range(N-1,self._N,-1): self._finv[i]=self._finv[i+1]*(i+1)%self._MOD
        self._N=N; return 1
    def fact(self,x): self._update(x) if x>self._N else None; return self._fact[x]
    def finv(self,x): self._update(x) if x>self._N else None; return self._finv[x]
    def modinv(self,x): return self._inv[x] if x<=self._invN else (-self._inv[self._MOD%x]*(self._MOD//x))%self._MOD if x> self._invN>=self._MOD%x else pow(x,self._MOD-2,self._MOD)
    def nCr(self,n,r): self._update(n); return 0 if any([n<r,n<0,r<0]) else self._fact[n]*self._finv[n-r]%self._MOD*self._finv[r]%self._MOD

MOD=998244353; nCr=MODnCr(10**6,MOD)
def solve(H,W):
    global MOD,nCr
    #DP[i][t]: i行目まで考える。i行目に設置した宝の数がt個となる場合の数
    DP=[[0]*3 for _ in range(H+1)]; DP[0][0]=1
    for h in range(1,H+1):
        DP[h][0]=sum(DP[h-1][x] for x in range(3))%MOD
        DP[h][1]=(DP[h-1][0]*W+DP[h-1][1]*(W-1)+DP[h-1][2]*(W-2))%MOD
        if W>=4:DP[h][2]=(DP[h-1][0]*(nCr.nCr(W,2)-W)+DP[h-1][1]*(nCr.nCr(W-1,2)-(W-2))+\
                          DP[h-1][2]*(nCr.nCr(W-2,2)-(W-4)))%MOD
    return sum(DP[-1])%MOD

for _ in range(int(input())):
    N,M=map(int,input().split())
    N,M=M,N  #なぜか交換するとうまくいった
    print(solve(N,M))
0