結果
| 問題 |
No.2250 Split Permutation
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2023-03-17 22:46:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 591 ms / 3,000 ms |
| コード長 | 9,323 bytes |
| コンパイル時間 | 431 ms |
| コンパイル使用メモリ | 81,824 KB |
| 実行使用メモリ | 111,156 KB |
| 最終ジャッジ日時 | 2024-09-18 11:56:27 |
| 合計ジャッジ時間 | 8,951 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
class Binary_Indexed_Tree():
def __init__(self, L, calc, unit, inv):
""" calc を演算とする N 項の Binary Indexed Tree を作成
calc: 演算 (2変数関数, 可換群)
unit: 群 calc の単位元 (x+e=e+x=x を満たす e)
inv : 群 calc の逆元 (1変数関数, x+inv(x)=inv(x)+x=e をみたす inv(x))
"""
self.calc=calc
self.unit=unit
self.inv=inv
self.N=N=len(L)
self.log=N.bit_length()-1
X=[unit]*(N+1)
for i in range(N):
p=i+1
X[p]=calc(X[p],L[i])
q=p+(p&(-p))
if q<=N:
X[q]=calc(X[q], X[p])
self.data=X
def get(self, k):
""" 第 k 要素の値を出力する.
k : 数列の要素
index: 先頭の要素の番号
"""
return self.sum(k, k)
def add(self, k, x):
""" 第 k 要素に x を加え, 更新を行う.
k : 数列の要素
x : 加える値
"""
data=self.data; calc=self.calc
p=k+1
while p<=self.N:
data[p]=calc(self.data[p], x)
p+=p&(-p)
def update(self, k, x):
""" 第 k 要素を x に変え, 更新を行う.
k: 数列の要素
x: 更新後の値
"""
a=self.get(k)
y=self.calc(self.inv(a), x)
self.add(k,y)
def sum(self, l, r):
""" 第 l 要素から第 r 要素までの総和を求める.
※ l != 0 を使うならば, 群でなくてはならない.
l: 始まり
r: 終わり
"""
l=l+1 if 0<=l else 1
r=r+1 if r<self.N else self.N
if l>r:
return self.unit
elif l==1:
return self.__section(r)
else:
return self.calc(self.inv(self.__section(l-1)), self.__section(r))
def __section(self, x):
""" B[0]+...+B[x] を求める. """
data=self.data; calc=self.calc
S=self.unit
while x>0:
S=calc(data[x], S)
x-=x&(-x)
return S
def all_sum(self):
return self.sum(0, self.N-1)
def binary_search(self, cond):
""" cond(B[0]+...+B[k]) が True となるような最小の k を返す.
cond: 単調増加
※ cond(unit)=True の場合の返り値は -1 とする.
※ cond(B[0]+...+B[k]) なる k が (0<=k<N に) 存在しない場合の返り値は N とする.
"""
if cond(self.unit):
return -1
j=0
r=self.N
t=1<<self.log
data=self.data; calc=self.calc
alpha=self.unit
while t>0:
if j+t<=self.N:
beta=calc(alpha, data[j+t])
if not cond(beta):
alpha=beta
j+=t
t>>=1
return j
def __getitem__(self, index):
if isinstance(index, int):
return self.get(index)
else:
return [self.get(t) for t in index]
def __setitem__(self, index, val):
self.update(index, val)
def __iter__(self):
for k in range(self.N):
yield self.sum(k, k)
#==================================================
class Permutation():
def __init__(self, n, p=[]):
if p==[]:
self.p=[i for i in range(n)]
self.ind=[i for i in range(n)]
else:
self.p=p
self.ind=[0]*n
for i in range(n):
self.ind[p[i]]=i
self.n=n
def __getitem__(self, k):
return self.p[k]
def __str__(self):
return str(self.p)
def __repr__(self):
return "[Permutation] : "+str(self)
def __eq__(self,other):
return (self.n==other.n) and (self.p==other.p)
def __iter__(self):
return iter(self.p)
def index(self, x):
return self.ind[x]
def __mul__(self,other):
assert self.n==other.n
p=self.p; q=other.p
return Permutation(self.n, [p[q[i]] for i in range(self.n)])
def __pow__(self, n):
if n<0:
return pow(self,-n).inverse()
a=list(range(self.n))
e=self.p[:]
while n:
if n&1:
a=[a[e[i]] for i in range(self.n)]
e=[e[e[i]] for i in range(self.n)]
n>>=1
return Permutation(self.n, a)
def __truediv__(self,other):
pass
def sgn(self):
""" 置換の符号を求める (偶置換 → 1, 奇置換 → -1)
"""
return -1 if self.minimum_transposition()%2 else 1
def inverse(self):
return Permutation(self.n, self.ind)
def inversion(self):
""" 転倒数を求める.
"""
BIT=[0]*(self.n+1)
Y=(self.n*(self.n-1))//2
for a in self.p:
s=a
while 1<=s:
Y-=BIT[s]
s-=s&(-s)
r=a+1
while r<=self.n:
BIT[r]+=1
r+=r&(-r)
return Y
def swap(self, i, j):
""" i 番目と j 番目を交換する ※ i と j を交換ではない"""
u=self.p[i]; v=self.p[j]
self.p[i]=v; self.p[j]=u
self.ind[v]=i; self.ind[u]=j
def transposition(self, u, v):
""" u と v を交換する ※ u 番目とv 番目ではない"""
a=self.ind[u]; b=self.ind[v]
self.p[a]=v; self.p[b]=u
self.ind[u]=b; self.ind[v]=a
def minimum_transposition(self):
""" 互換の最小回数を求める. """
return self.n-len(self.cycle_division())
def cycle_division(self, mode=True):
""" 置換を巡回置換の積に分解する.
mode: 自己ループを入れるか否か"""
p=self.p
T=[False]*self.n
A=[]
for k in range(self.n):
if not T[k]:
a=[k]
T[k]=True
v=p[k]
while v!=k:
T[v]=True
a.append(v)
v=p[v]
if mode or len(a)>=2:
A.append(a)
return A
def operate_list(self, list):
assert self.n==len(list),"置換の長さとリストの長さが違います."
return [list[self.ind[i]] for i in range(self.n)]
def order(self, mod=None):
""" 位数を求める (mod を指定すると, mod で割った余りになる).
"""
from math import gcd
if mod==None:
x=1
for m in self.cycle_division():
g=gcd(x,len(m))
x=(x//g)*len(m)
return x
else:
def factor(n):
e=(n&(-n)).bit_length()-1
yield 2,e
n>>=e
p=3
while p*p<=n:
if n%p==0:
e=0
while n%p==0:
n//=p
e+=1
yield p,e
p+=2
if n>1:
yield n,1
return
T={}
for m in self.cycle_division():
for p,e in factor(len(m)):
T[p]=max(T.get(p,0), e)
x=1
for p in T:
x*=pow(p, T[p], mod)
x%=mod
return x
def conjugate(self):
return Permutation(self.n, [self.n-1-x for x in self.p])
def next(self):
y=[]
for i in range(self.n-1,0,-1):
y.append(self.p[i])
if self.p[i-1]<self.p[i]:
y.append(self.p[i-1])
a=self.p[i-1]
break
x=self.p[:i-1]
y.sort()
for j,b in enumerate(y):
if a<b:
x.append(b)
del y[j]
break
return Permutation(self.n, x+y)
#=================================================
def Permutation_Inversion(P, Q):
""" P から Q へ隣接項同士の入れ替えのみの最小回数を求める.
"""
R=Q*(P.inverse())
return R.inversion()
def List_Inversion(A, B, default=-1):
"""長さが等しいリスト A,B に対して, 以下の操作の最小回数を求める.
列 A[i] と A[i+1] を入れ替え, B と一致させる.
"""
from collections import defaultdict
if len(A)!=len(B):
return default
N=len(A)
D=defaultdict(list)
for i in range(N):
D[A[i]].append(i)
for lis in D:
D[lis].reverse()
try:
return Permutation(N,[D[B[i]].pop() for i in range(N)]).inversion()
except:
return default
#==================================================
def solve():
from operator import add,neg
N=int(input())
P=[0]+list(map(int,input().split()))
Mod=998244353
B=Binary_Indexed_Tree([0]*(N+1), add, 0, neg)
for j in range(1,N+1):
B.add(P[j],pow(2,j*(Mod-2),Mod))
X=Permutation(N+1,P).inversion()*pow(2,N-1,Mod)
for i in range(1,N+1):
X-=B.sum(1,P[i]-1)*pow(2,N-1+i,Mod)%Mod; X%=Mod
B.update(P[i],0)
return X
#==================================================
print(solve())