結果

問題 No.3052 Increasing Sliding Window Minimum
コンテスト
ユーザー PNJ
提出日時 2025-03-07 22:22:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,251 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 276,756 KB
最終ジャッジ日時 2025-03-07 22:22:55
合計ジャッジ時間 24,021 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
  if n == 2:
    if A == [-1, -1]:
      print(2)
    else:
      print(1)
    return
  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]
    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
      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][j] * fact[i - j] % mod for j in range(n + 1)]
      for k in range(1, i + 1):
        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
      f = [dp[i - 1][j] * fact[i - 1 - j] % mod for j in range(n + 1)]
      for k in range(1, i + 1):
        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