結果

問題 No.3052 Increasing Sliding Window Minimum
コンテスト
ユーザー titia
提出日時 2025-03-12 08:35:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,835 bytes
コンパイル時間 504 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 665,356 KB
最終ジャッジ日時 2025-03-12 08:36:02
合計ジャッジ時間 7,905 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 33 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

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+2)
    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)


    B=A[:]
    ind=0

    for i in range(n):
        if B[i]==-1:
            B[i]=LIST[ind]
            ind+=1

    flag=1
    nowmax=-1

    for i in range(n-1):
        x=min(B[i],B[i+1])

        if nowmax>x:
            flag=0
            break
        else:
            nowmax=x

    if flag==0:
        print(0)
        continue
        

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


    DP1=[[0]*(n+1) for i in range(n+1)]
    DP1A=[[0]*(n+1) for i in range(n+1)]
    DP2=[[0]*(n+1) for i in range(n+1)]
    DP1[0][0]=1
    
    # DP[i][j]で、index i-1まで見て、使っていない個数がj個
    # DP1は、iやi+1のどちらかに置く
    # DP1Aは、DP1のための補助配列。jを消す遷移のみを行う。
    # DP2は、iに必ず置く

    for i in range(n+1):
        for j in range(n,-1,-1):

            now=DP1A[i][j]

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

            if i==n:
                continue
                    
            now=DP2[i][j]

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

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

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

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

                    
    print(DP1[n][0]%mod)
0