結果

問題 No.3052 Increasing Sliding Window Minimum
コンテスト
ユーザー titia
提出日時 2025-03-11 08:09:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,912 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 469,016 KB
最終ジャッジ日時 2025-03-11 08:09:28
合計ジャッジ時間 10,746 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

mod=998244353

F=[1]
for i in range(1,5050):
    F.append(F[-1]*i%mod)

T=int(input())

for tests in range(T):
    n=int(input())
    A=list(map(int,input().split()))

    KO=[0]*n
    
    for i in range(n):
        if A[i]!=-1:
            A[i]-=1
        else:
            KO[i]+=1

    for i in range(1,n):
        KO[i]+=KO[i-1]

    KO=[0]+KO

    MAX=0
    flag=1
    
    for i in range(n-1):
        if A[i]!=-1 and A[i+1]!=-1:
            x=min(A[i],A[i+1])

            if MAX<=x:
                MAX=x
            else:
                flag=0
                break

    if flag==0:
        print(0)
        continue

    MINLIST=[1<<30]*(n+1)
    for i in range(n-1,-1,-1):
        MINLIST[i]=min(MINLIST[i],MINLIST[i+1])
        if A[i]!=-1:
            MINLIST[i]=min(MINLIST[i],A[i])


    USE=[0]*n
    for a in A:
        if a!=-1:
            USE[a]=1

    LIST=[]
    for i in range(n):
        if USE[i]==0:
            LIST.append(i)

    if LIST==[]:
        print(1)
        continue

    DP1=[[0]*n for i in range(n+1)]
    DP2=[[0]*n for i in range(n+1)]
    DP1[0][0]=1
    
    # DP[i][j]で、index i-1まで見て、使っていない個数がj個
    # DP1は、iやi+1のどちらかに置く
    # DP2は、iに必ず置く

    for i in range(n):
        for j in range(i,-1,-1):
            now=DP2[i][j]

            if now!=0:
                #if j>=1:
                #    DP2[i][j-1]+=now*j
                #    DP2[i][j-1]%=mod

                if KO[i]-j<len(LIST):
                    nec=LIST[KO[i]-j]
                else:
                    nec=10**6

                if A[i]==-1 and nec<MINLIST[i]:
                    DP1[i+1][j]+=now
                    DP1[i+1][j]%=mod
                else:
                    pass
                    #if A[i]<nec:
                    #    DP1[i+1][j]+=now
                    #    DP1[i+1][j]%=mod

            now=DP1[i][j]

            if now!=0:
                if j>=1:
                    DP1[i][j-1]+=now*j
                    DP1[i][j-1]%=mod

                if KO[i]-j<len(LIST):
                    nec=LIST[KO[i]-j]
                else:
                    nec=10**6

                #print("!",i,j,now,nec)

                if A[i]==-1 and nec<MINLIST[i+1]:
                    DP1[i+1][j]+=now
                    DP1[i+1][j]%=mod
                    DP2[i+1][j+1]+=now
                    DP2[i+1][j+1]%=mod
                elif A[i]!=-1:
                    if A[i]>nec:
                        DP2[i+1][j]+=now
                        DP2[i+1][j]%=mod
                    else:
                        DP1[i+1][j]+=now
                        DP1[i+1][j]%=mod



    ANS=0

    for i in range(n):
        dp=DP1[n][i]
        ANS+=dp*F[i]%mod
        ANS%=mod

    print(ANS)
0