結果

問題 No.2250 Split Permutation
ユーザー 👑 KazunKazun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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())
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0