結果

問題 No.3052 Increasing Sliding Window Minimum
コンテスト
ユーザー PNJ
提出日時 2025-03-07 22:34:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,563 bytes
コンパイル時間 430 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 277,000 KB
最終ジャッジ日時 2025-03-07 22:35:03
合計ジャッジ時間 24,201 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353
n = 20000
inv = [1 for j in range(n + 1)]
for a in range(2, n + 1):
  # ax + py = 1 <=> rx + p(-x - qy) = -q => x = -(inv[r]) * (p // a)  (r = p % a)
  res = (mod - inv[mod % a]) * (mod // a)
  inv[a] = res % mod

def mod_inv(a, mod = 998244353):
  if mod == 1:
    return 0
  a %= mod
  b, s, t = mod, 1, 0
  while True:
    if a == 1:
      return s
    t -= (b // a) * s
    b %= a
    if b == 1:
      return t + mod
    s -= (a // b) * t
    a %= b

fact = [1 for i in range(n + 1)]
for i in range(1, n + 1):
  fact[i] = fact[i - 1] * i % mod

fact_inv = [1 for i in range(n + 1)]
fact_inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(n, 0, -1):
  fact_inv[i - 1] = fact_inv[i] * i % mod

for i in range(n):
  fact.append(0)
  fact_inv.append(0)

def solve():
  n = int(input())
  A = list(map(int, input().split()))
  dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
  dp[0][0] = 1
  appear = [0 for _ in range(n + 5)]
  for i in range(n):
    appear[A[i]] = 1
  for i in range(n):
    p = A[i]
    q = A[i - 1]
    if p == -1:
      f = [dp[i][j] * fact[i - j] % mod for j in range(n + 1)]
      for k in range(1, i + 2):
        f[k] = (f[k] + f[k - 1]) % mod
        if appear[k]:
          continue
        dp[i + 1][k] = f[k - 1] * fact_inv[i + 1 - k] % mod
      if i == 0:
        continue
      if q == -1:
        f = [dp[i - 1][j] * fact[i - 1 - j] % mod for j in range(n + 1)]
        for k in range(1, i + 2):
          f[k] = (f[k] + f[k - 1]) % mod
          if appear[k]:
            continue
          dp[i + 1][k] = (dp[i + 1][k] + f[k - 1] * fact_inv[i - k]) % mod
      else:
        f = [dp[i - 1][j] * fact[i - 1 - j] % mod for j in range(n + 1)]
        for k in range(1, min(i + 1, q - 1) + 1):
          f[k] = (f[k] + f[k - 1]) % mod
          if appear[k]:
            continue
          dp[i + 1][k] = (dp[i + 1][k] + f[k - 1] * fact_inv[i - k]) % mod
    else:
      f = [dp[i][j] * fact[i - j] % mod for j in range(n + 1)]
      for k in range(1, i + 2):
        f[k] = (f[k] + f[k - 1]) % mod
      dp[i + 1][p] = f[p - 1] * fact_inv[i + 1 - p] % mod
      if i == 0:
        continue
      if q != -1:
        if q < p:
          continue
      f = [dp[i - 1][j] * fact[i - 1 - j] % mod for j in range(n + 1)]
      for k in range(1, i + 2):
        f[k] = (f[k] + f[k - 1]) % mod
      dp[i + 1][p] = (dp[i + 1][p] + f[p - 1] * fact_inv[i - p]) % mod
  ans = 0
  for k in range(1, n + 1):
    ans = (ans + dp[n][k] * fact[n - k]) % mod
  print(ans)
  return

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