結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー titia
提出日時 2025-03-13 05:12:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 701 ms / 2,000 ms
コード長 1,503 bytes
コンパイル時間 389 ms
コンパイル使用メモリ 82,756 KB
実行使用メモリ 78,924 KB
最終ジャッジ日時 2025-03-13 05:12:28
合計ジャッジ時間 12,183 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

mod=998244353

T=int(input())

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

    if n==2 and A==[-1,-1]:
        print(2)
        continue

    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[min(1,n-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)
         
    print(DP[n-1]%mod)
0