結果

問題 No.3052 Increasing Sliding Window Minimum
コンテスト
ユーザー rin204
提出日時 2025-02-03 23:53:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 712 ms / 2,000 ms
コード長 1,425 bytes
コンパイル時間 897 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 87,680 KB
最終ジャッジ日時 2025-02-03 23:53:21
合計ジャッジ時間 13,172 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353


def solve():
    n = int(input())
    A = list(map(int, input().split()))[::-1]
    rem = [False] * n
    cc = 0
    for i in range(n):
        if A[i] == -1:
            continue
        A[i] -= 1
        rem[A[i]] = True
        cc += 1

    dp1 = [0] * n
    dp2 = [0] * n
    if A[0] == -1:
        for i in range(n):
            if not rem[i]:
                dp1[i] = 1
    else:
        dp1[A[0]] = 1
        cc -= 1
        rem[A[0]] = False

    for i, a in enumerate(A[1:], 1):
        ndp1 = [0] * n
        ndp2 = [0] * n
        if a != -1:
            tot = 0
            for j in range(a + 1, n):
                tot += dp1[j] + dp2[j]
            ndp1[a] = tot % MOD
            for j in range(a):
                ndp2[j] = dp1[j]
            rem[a] = False
            cc -= 1
        else:
            c2 = cc
            for j in range(n):
                if rem[j]:
                    c2 -= 1
                    continue

                x = n - 1 - j - (i - 1) - c2
                if x < 0:
                    continue
                ndp2[j] = dp1[j] * x % MOD

            tot = 0
            for j in range(n - 1, -1, -1):
                if rem[j]:
                    continue
                ndp1[j] = tot
                tot = (tot + dp1[j] + dp2[j]) % MOD
        dp1 = ndp1
        dp2 = ndp2

    print((dp1[0] + dp2[0]) % MOD)


for _ in range(int(input())):
    solve()
0