結果
問題 | No.2898 Update Max |
ユーザー | convexineq |
提出日時 | 2024-09-23 23:15:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 189 ms / 2,000 ms |
コード長 | 2,559 bytes |
コンパイル時間 | 3,422 ms |
コンパイル使用メモリ | 81,996 KB |
実行使用メモリ | 123,488 KB |
最終ジャッジ日時 | 2024-09-23 23:20:40 |
合計ジャッジ時間 | 12,451 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 57 ms
72,364 KB |
testcase_01 | AC | 56 ms
70,828 KB |
testcase_02 | AC | 54 ms
70,868 KB |
testcase_03 | AC | 77 ms
82,516 KB |
testcase_04 | AC | 74 ms
82,892 KB |
testcase_05 | AC | 74 ms
81,216 KB |
testcase_06 | AC | 75 ms
82,028 KB |
testcase_07 | AC | 109 ms
81,744 KB |
testcase_08 | AC | 186 ms
116,832 KB |
testcase_09 | AC | 180 ms
117,008 KB |
testcase_10 | AC | 182 ms
117,032 KB |
testcase_11 | AC | 185 ms
116,856 KB |
testcase_12 | AC | 181 ms
116,932 KB |
testcase_13 | AC | 185 ms
117,996 KB |
testcase_14 | AC | 185 ms
118,056 KB |
testcase_15 | AC | 184 ms
117,844 KB |
testcase_16 | AC | 189 ms
118,292 KB |
testcase_17 | AC | 188 ms
117,880 KB |
testcase_18 | AC | 187 ms
123,160 KB |
testcase_19 | AC | 185 ms
123,488 KB |
testcase_20 | AC | 188 ms
123,132 KB |
testcase_21 | AC | 187 ms
123,144 KB |
testcase_22 | AC | 187 ms
123,424 KB |
testcase_23 | AC | 157 ms
121,820 KB |
testcase_24 | AC | 159 ms
121,728 KB |
testcase_25 | AC | 159 ms
121,628 KB |
testcase_26 | AC | 160 ms
121,464 KB |
testcase_27 | AC | 162 ms
121,652 KB |
testcase_28 | AC | 154 ms
122,132 KB |
testcase_29 | AC | 58 ms
72,212 KB |
testcase_30 | AC | 56 ms
71,888 KB |
ソースコード
class BIT: #0-indexed __slots__ = ["size", "tree","depth","n0"] def __init__(self, n): self.size = n self.tree = [0]*(n+1) self.depth = n.bit_length() self.n0 = 1<<self.depth def get_sum(self, i): #a_0 + ... + a_{i} #閉区間 s = 0; i += 1 while i > 0: s += self.tree[i] i -= i & -i return s def range_sum(self,l,r): #a_l + ... + a_r 閉区間 return self.get_sum(r) - self.get_sum(l-1) def range_sum_larger(self,l): #a_l + ... (端まで) return self.get_sum(self.size-1) - (self.get_sum(l-1) if l else 0) def add(self, i, x): i += 1 while i <= self.size: self.tree[i] += x i += i & -i SIZE=5*10**5+1; MOD=998244353 #10**9+7 #ここを変更する inv = [0]*SIZE # inv[j] = j^{-1} mod MOD fac = [0]*SIZE # fac[j] = j! mod MOD finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD fac[0] = fac[1] = 1 finv[0] = finv[1] = 1 for i in range(2,SIZE): fac[i] = fac[i-1]*i%MOD finv[-1] = pow(fac[-1],MOD-2,MOD) for i in range(SIZE-1,0,-1): finv[i-1] = finv[i]*i%MOD inv[i] = finv[i]*fac[i-1]%MOD def choose(n,r): # nCk mod MOD の計算 if 0 <= r <= n: return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD else: return 0 def perm(n,r): # nPr mod MOD if 0 <= r <= n: return fac[n]*finv[n-r]%MOD else: return 0 import sys readline = sys.stdin.readline #n = int(readline()) #n,Q = map(int,readline().split()) n = int(readline()) *a, = map(int,readline().split()) # from itertools import permutations # cnt = [0]*n # for lst in permutations(list(range(1,n+1))): # for i in range(n): # if a[i] != -1 and lst[i] != a[i]: break # else: # m = 0 # for i in range(n): # m = max(m,lst[i]) # if m==lst[i]: cnt[i] += 1 # print(cnt) bit = BIT(n+1) for i in range(1,n+1): bit.add(i,1) for ai in a: if ai != -1: bit.add(ai,-1) tot = a.count(-1) ans = 0 m = 0 cnt = 0 for i,ai in enumerate(a): if ai == -1: cnt += 1 c = bit.get_sum(m) r = (fac[tot]-perm(c,cnt)*fac[tot-cnt])%MOD*inv[cnt] #print((perm(m-i-1+cnt,cnt)*fac[tot-cnt])%MOD,r%MOD) #print(r%MOD) ans = (ans+r)%MOD else: if m < ai: c = bit.get_sum(ai) r = perm(c,cnt)*fac[tot-cnt] #print(r) ans = (ans+r)%MOD m = ai else: r = 0 #print(r%MOD) print(ans)