結果

問題 No.2792 Security Cameras on Young Diagram
コンテスト
ユーザー navel_tos
提出日時 2024-06-21 22:53:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 3,057 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,484 KB
実行使用メモリ 92,672 KB
最終ジャッジ日時 2024-06-24 18:46:06
合計ジャッジ時間 2,420 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 2792 Security Cameras on Young Diagram

#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



#入力受取
N = int(input())
A = list(map(int, input().split()))
MOD = 998244353
nCr = MODnCr(N * 2, MOD)

#愚直解を書く
'''
#DP[i][j]: A[i]行目の監視カメラの置き方を決める直前であって、j列目まで縦で監視されている
DP = [[0] * (A[0] + 1) for _ in range(N + 1)]
DP[0][0] = 1
for i, Ai in enumerate(A):
    #もらうDPの場合
    for k in range(Ai + 1):
        for j in range(k + 1):
            DP[i + 1][k] += DP[i][j]
            DP[i + 1][k] %= MOD
    for j in range(Ai + 1, A[i - 1] + 1):  #配列外参照あり
        DP[i + 1][Ai] += DP[i][j]
        DP[i + 1][Ai] %= MOD
print(sum(DP[-1]))

#高速化
ans = 0
DP = [[0] * (A[0] + 1) for _ in range(N + 1)]
DP[0][0] = 1
for i, Ai in enumerate(A):
    for k in range(Ai + 1):
        DP[i + 1][k] = sum(DP[i][j] for j in range(k + 1)) % MOD
    ans += sum(DP[i][j] for j in range(Ai + 1, A[i - 1] + 1)) % MOD
    ans %= MOD
print((sum(DP[-1]) + ans) % MOD)
'''

#エスパーしたのでやる
#DP[i][j]: comb(i + j - 1, j) if i > 0 else 1, 0, 0, ･･･
#DP = [[1] + [0] * A[0]] + [[nCr.nCr(i + j - 1, j) for j in range(A[0] + 1)] for i in range(1, N + 1)]
#ans = sum(DP[N][j] for j in range(A[-1] + 1)) % MOD
ans = sum(nCr.nCr(N + j - 1, j) for j in range(A[-1] + 1)) % MOD
for i in range(N):
    for j in range(A[i] + 1, A[i - 1] + 1):
        #ans += DP[i][j]
        ans += nCr.nCr(i + j - 1, j)
        ans %= MOD
print(ans % MOD)
0