結果

問題 No.3052 Increasing Sliding Window Minimum
コンテスト
ユーザー titia
提出日時 2025-03-13 05:04:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,469 bytes
コンパイル時間 651 ms
コンパイル使用メモリ 82,028 KB
実行使用メモリ 79,044 KB
最終ジャッジ日時 2025-03-13 05:05:10
合計ジャッジ時間 13,627 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 41 WA * 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()))

    for i in range(n):
        if A[i]!=-1:
            A[i]-=1

    B=[-1]*n
    MIKO=[0]*n

    for i in range(n):
        if A[i]!=-1:
            B[A[i]]=i
        else:
            MIKO[i]+=1

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

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

    L=[-1]*n
    now=0
    for x in LIST:
        now+=1
        L[x]=now
            

    DP=[0]*n
    DP[1]=1
    # index iまで置くことが可能なときの個数

    for i in range(n):
        # iはこれから置く数字
        NDP=[0]*n
        
        if B[i]==-1:
            for j in range(n):
                if A[j]==-1:
                    NDP[min(n-1,j+2)]+=DP[j]
                if j-1>=0 and A[j-1]==-1:
                    NDP[min(n-1,j+1)]+=DP[j]
                if j-2>=0:
                    NDP[j]+=(MIKO[j-2]-(L[i]-1))*DP[j]
                    # MIKO[j-2]-iはj-2までで-1のままの個数
        else:
            x=B[i]
            for j in range(n):
                if x<=j:
                    NDP[min(n-1,max(j,x+2))]+=DP[j]

        DP=[x%mod for x in NDP]
         
    print(DP[n-1]%mod)
0