結果
問題 | No.1712 Read and Pile |
ユーザー | chineristAC |
提出日時 | 2021-05-10 23:39:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 783 ms / 2,000 ms |
コード長 | 2,823 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 81,860 KB |
実行使用メモリ | 131,264 KB |
最終ジャッジ日時 | 2023-10-17 19:44:20 |
合計ジャッジ時間 | 18,451 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
58,124 KB |
testcase_01 | AC | 47 ms
58,124 KB |
testcase_02 | AC | 46 ms
58,124 KB |
testcase_03 | AC | 47 ms
58,124 KB |
testcase_04 | AC | 47 ms
58,124 KB |
testcase_05 | AC | 47 ms
58,124 KB |
testcase_06 | AC | 47 ms
58,124 KB |
testcase_07 | AC | 46 ms
58,124 KB |
testcase_08 | AC | 462 ms
105,444 KB |
testcase_09 | AC | 632 ms
105,848 KB |
testcase_10 | AC | 443 ms
105,284 KB |
testcase_11 | AC | 530 ms
105,492 KB |
testcase_12 | AC | 366 ms
106,024 KB |
testcase_13 | AC | 480 ms
102,940 KB |
testcase_14 | AC | 427 ms
109,840 KB |
testcase_15 | AC | 569 ms
105,640 KB |
testcase_16 | AC | 559 ms
103,708 KB |
testcase_17 | AC | 498 ms
106,336 KB |
testcase_18 | AC | 533 ms
105,924 KB |
testcase_19 | AC | 474 ms
108,736 KB |
testcase_20 | AC | 479 ms
110,032 KB |
testcase_21 | AC | 587 ms
106,588 KB |
testcase_22 | AC | 495 ms
105,408 KB |
testcase_23 | AC | 634 ms
112,176 KB |
testcase_24 | AC | 582 ms
112,012 KB |
testcase_25 | AC | 648 ms
112,164 KB |
testcase_26 | AC | 750 ms
131,264 KB |
testcase_27 | AC | 783 ms
131,256 KB |
testcase_28 | AC | 419 ms
104,992 KB |
testcase_29 | AC | 624 ms
107,528 KB |
testcase_30 | AC | 477 ms
110,636 KB |
testcase_31 | AC | 229 ms
119,756 KB |
testcase_32 | AC | 210 ms
108,044 KB |
testcase_33 | AC | 439 ms
104,148 KB |
testcase_34 | AC | 447 ms
102,724 KB |
testcase_35 | AC | 681 ms
108,064 KB |
testcase_36 | AC | 744 ms
109,504 KB |
testcase_37 | AC | 694 ms
105,464 KB |
testcase_38 | AC | 48 ms
58,124 KB |
testcase_39 | AC | 71 ms
87,212 KB |
testcase_40 | AC | 76 ms
91,928 KB |
testcase_41 | AC | 88 ms
93,348 KB |
testcase_42 | AC | 96 ms
101,344 KB |
ソースコード
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(M): 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!=-1 and A[i]!=pre: res += 1 res %= mod elif pre==-1: 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))