結果

問題 No.2898 Update Max
コンテスト
ユーザー lmxyue
提出日時 2025-09-03 15:18:14
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 894 ms / 2,000 ms
コード長 1,214 bytes
コンパイル時間 488 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 37,112 KB
最終ジャッジ日時 2025-09-03 15:18:31
合計ジャッジ時間 17,007 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

md = 998244353;
N = int(input())
A = list(map(int, input().split()))
kai = [1] * (N+1)
fkai = [1] * (N + 1)
for i in range(1, N+1) :
        kai[i] = kai[i - 1] * i
        kai[i] %= md
fkai[N] = pow(kai[N], -1, md);
for i in range(N, 0, -1) :
        fkai[i-1] = fkai[i] * i
        fkai[i-1] %= md
def comb(n, r) :
        if r < 0 or n < r :
                return 0
        return (kai[n] * fkai[r] * fkai[n - r]) % md

cnt = [0] * (N + 1)
for a in A :
        if a > 0 :
                cnt[a] += 1
res = []
for i in range(1, N+1) :
        if cnt[i] == 0 :
                res.append(i)
res.append(N+100)
siz = len(res) - 1
ans = 0
mi = 0
fl = 0
m1 = 0
for a in A :
        mi = max(mi, a)
        while (res[fl] < mi) :
                fl += 1
        if a == mi :
                p = comb(fl, m1)
                p *= kai[m1]
                p %= md
                p *= kai[siz - m1]
                p %= md
                ans += p
        if a == -1 :
                p = md + comb(siz, m1+1) - comb(fl, m1+1)
                p *= kai[m1]
                p %= md
                p *= kai[siz - m1 - 1]
                p %= md
                ans += p
                m1 += 1
        ans %= md
print(ans)
0