結果
問題 | No.1712 Read and Pile |
ユーザー | chineristAC |
提出日時 | 2021-05-10 23:36:19 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,833 bytes |
コンパイル時間 | 492 ms |
コンパイル使用メモリ | 81,592 KB |
実行使用メモリ | 131,256 KB |
最終ジャッジ日時 | 2023-10-17 19:42:59 |
合計ジャッジ時間 | 18,217 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
58,092 KB |
testcase_01 | RE | - |
testcase_02 | AC | 48 ms
58,112 KB |
testcase_03 | AC | 48 ms
58,112 KB |
testcase_04 | AC | 49 ms
58,112 KB |
testcase_05 | AC | 48 ms
58,112 KB |
testcase_06 | AC | 48 ms
58,112 KB |
testcase_07 | AC | 48 ms
58,112 KB |
testcase_08 | AC | 503 ms
105,440 KB |
testcase_09 | AC | 659 ms
105,848 KB |
testcase_10 | AC | 458 ms
105,288 KB |
testcase_11 | AC | 563 ms
105,492 KB |
testcase_12 | AC | 381 ms
106,024 KB |
testcase_13 | AC | 494 ms
102,940 KB |
testcase_14 | AC | 446 ms
109,840 KB |
testcase_15 | AC | 566 ms
105,640 KB |
testcase_16 | AC | 557 ms
103,708 KB |
testcase_17 | AC | 515 ms
106,336 KB |
testcase_18 | AC | 541 ms
105,924 KB |
testcase_19 | AC | 480 ms
108,736 KB |
testcase_20 | AC | 478 ms
110,032 KB |
testcase_21 | AC | 593 ms
106,588 KB |
testcase_22 | AC | 501 ms
105,408 KB |
testcase_23 | AC | 631 ms
112,176 KB |
testcase_24 | AC | 582 ms
112,016 KB |
testcase_25 | AC | 658 ms
112,168 KB |
testcase_26 | AC | 743 ms
131,256 KB |
testcase_27 | AC | 774 ms
131,248 KB |
testcase_28 | AC | 414 ms
104,992 KB |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | AC | 433 ms
107,384 KB |
testcase_34 | AC | 442 ms
110,544 KB |
testcase_35 | AC | 675 ms
108,064 KB |
testcase_36 | AC | 742 ms
109,492 KB |
testcase_37 | AC | 693 ms
105,464 KB |
testcase_38 | AC | 47 ms
58,112 KB |
testcase_39 | AC | 71 ms
86,888 KB |
testcase_40 | AC | 74 ms
89,564 KB |
testcase_41 | WA | - |
testcase_42 | WA | - |
ソースコード
class BIT(): def __init__(self,n,mod=None): self.BIT=[0]*(n+1) self.num=n self.mod = mod def query(self,idx): res_sum = 0 while idx > 0: res_sum += self.BIT[idx] if self.mod: res_sum %= self.mod idx -= idx&(-idx) return res_sum #Ai += x O(logN) def update(self,idx,x): while idx <= self.num: self.BIT[idx] += x if self.mod: self.BIT[idx] %= self.mod idx += idx&(-idx) return import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) mod = 998244353 i2 = pow(2,mod-2,mod) def solve(N,M,A): assert 1<=N<=2*10**5 assert 1<=M<=2*10**5 for i in range(N): if A[i]!=-1: assert 1<=A[i]<=N if N==1: return M if N==2: res = M pre = 1 Z = A.count(-1) for i in range(M): if A[i]==-1: res += i2 res %= mod else: if pre!=0 and A[i]!=pre: res += 1 res %= mod elif pre==0: res += i2 res %= mod pre = A[i] return res p = ((N-2)*pow(N,mod-2,mod)) % mod ip = pow(p,mod-2,mod) pow_p = [1 for i in range(N+M+1)] pow_ip = [1 for i in range(N+M+1)] for i in range(1,N+M+1): pow_p[i] = (pow_p[i-1] * p) % mod pow_ip[i] = (pow_ip[i-1] * ip) % mod A = [N-i for i in range(N)] + A A = [-100] + A zero = [A[i]==-1 for i in range(N+M+1)] for i in range(1,N+M+1): zero[i] += zero[i-1] lastappear = [N-i+1 for i in range(N+1)] res = 0 bit_p = BIT(N+M,mod=998244353) bit_cnt = BIT(N+M) for i in range(1,N+1): bit_cnt.update(i,1) bit_p.update(i,pow_ip[zero[i]]) for i in range(N+1,N+M+1): if A[i]==-1: res += (N-1) res %= mod else: pre = lastappear[A[i]] k = bit_cnt.query(pre-1) res = (res + N-1) % mod res += (bit_p.query(i)-bit_p.query(pre)) * pow_p[zero[i]] % mod res %= mod res -= k * pow_p[zero[i]-zero[pre]] % mod res %= mod bit_cnt.update(pre,-1) bit_p.update(pre,-pow_ip[zero[pre]]) lastappear[A[i]] = i bit_cnt.update(i,1) bit_p.update(i,pow_ip[zero[i]]) res *= i2 res %= mod res += M res %= mod return res N,M = mi() A = li() print(solve(N,M,A))