結果

問題 No.2898 Update Max
コンテスト
ユーザー PNJ
提出日時 2024-09-20 23:19:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,187 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 135,748 KB
最終ジャッジ日時 2024-09-20 23:19:50
合計ジャッジ時間 8,937 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353
n = 10**6
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

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

def binom(n,r):
  if n < r or n < 0 or r < 0:
    return 0
  res = fact_inv[n-r] * fact_inv[r] % mod
  res *= fact[n]
  res %= mod
  return res

N = int(input())
A = list(map(int,input().split()))
X = [0 for i in range(N)]
Q = [-1 for i in range(N + 1)]
for i in range(N):
  if A[i] == -1:
    X[i] += 1
  if i > 0:
    X[i] += X[i - 1]
  else:
    Q[A[i]] = i

S = set(A)
R = []
for i in range(1,N + 1):
  if i not in S:
    R.append(i)
n = len(R)

M = X[-1]
m = M
j = M
ans = 0
for i in range(N,-1,-1):
  if Q[i] == -1:
    res = fact[j - 1] * fact[M - j] % mod
    ans = (ans + res * binom(M + 1,j) % mod) % mod
    j -= 1
  else:
    n = X[Q[i]]
    ans = (ans + fact[m] * binom(n,m) % mod + fact[X[-1] - n]) % mod
    M = min(M,n)
print(ans)
0