結果
問題 | No.2250 Split Permutation |
ユーザー |
|
提出日時 | 2023-03-17 21:53:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 616 ms / 3,000 ms |
コード長 | 1,435 bytes |
コンパイル時間 | 369 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 109,696 KB |
最終ジャッジ日時 | 2024-09-18 10:46:04 |
合計ジャッジ時間 | 9,248 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#ごめんなさいpypy遅くないですimport sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import gcd,loginput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())class BIT():def __init__(self,n,mod=0):self.BIT = [0]*(n+1)self.num = nself.mod = mod"""return A[1] + A[2] + ... A[idx] in O(log n)"""def query(self,idx):res_sum = 0mod = self.modwhile idx > 0:res_sum += self.BIT[idx]if mod:res_sum %= modidx -= idx&(-idx)return res_sum"""A[idx] += in O(log n)"""def update(self,idx,x):mod = self.modwhile idx <= self.num:self.BIT[idx] += xif mod:self.BIT[idx] %= modidx += idx&(-idx)returnmod = 998244353N = int(input())P = li()fw = BIT(N,mod=998244353)fw2 = BIT(N)res = 0S = 0i2 = pow(2,mod-2,mod)inv = 0for i in range(N):tmp = S - fw.query(P[i])res += tmp * pow(i2,i,mod) % modres %= modinv += i - fw2.query(P[i])fw.update(P[i],pow(2,i,mod))S += pow(2,i,mod)fw2.update(P[i],1)minus = res * pow(2,N-1,mod) % modans = inv * pow(2,N-1,mod) % modprint((ans-minus) % mod)