結果

問題 No.2898 Update Max
ユーザー PNJPNJ
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

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