結果
問題 | No.2250 Split Permutation |
ユーザー |
👑 ![]() |
提出日時 | 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=calcself.unit=unitself.inv=invself.N=N=len(L)self.log=N.bit_length()-1X=[unit]*(N+1)for i in range(N):p=i+1X[p]=calc(X[p],L[i])q=p+(p&(-p))if q<=N:X[q]=calc(X[q], X[p])self.data=Xdef 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.calcp=k+1while 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 1r=r+1 if r<self.N else self.Nif l>r:return self.unitelif 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.calcS=self.unitwhile x>0:S=calc(data[x], S)x-=x&(-x)return Sdef 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 -1j=0r=self.Nt=1<<self.logdata=self.data; calc=self.calcalpha=self.unitwhile t>0:if j+t<=self.N:beta=calc(alpha, data[j+t])if not cond(beta):alpha=betaj+=tt>>=1return jdef __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=pself.ind=[0]*nfor i in range(n):self.ind[p[i]]=iself.n=ndef __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.np=self.p; q=other.preturn 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>>=1return Permutation(self.n, a)def __truediv__(self,other):passdef sgn(self):""" 置換の符号を求める (偶置換 → 1, 奇置換 → -1)"""return -1 if self.minimum_transposition()%2 else 1def inverse(self):return Permutation(self.n, self.ind)def inversion(self):""" 転倒数を求める."""BIT=[0]*(self.n+1)Y=(self.n*(self.n-1))//2for a in self.p:s=awhile 1<=s:Y-=BIT[s]s-=s&(-s)r=a+1while r<=self.n:BIT[r]+=1r+=r&(-r)return Ydef swap(self, i, j):""" i 番目と j 番目を交換する ※ i と j を交換ではない"""u=self.p[i]; v=self.p[j]self.p[i]=v; self.p[j]=uself.ind[v]=i; self.ind[u]=jdef transposition(self, u, v):""" u と v を交換する ※ u 番目とv 番目ではない"""a=self.ind[u]; b=self.ind[v]self.p[a]=v; self.p[b]=uself.ind[u]=b; self.ind[v]=adef minimum_transposition(self):""" 互換の最小回数を求める. """return self.n-len(self.cycle_division())def cycle_division(self, mode=True):""" 置換を巡回置換の積に分解する.mode: 自己ループを入れるか否か"""p=self.pT=[False]*self.nA=[]for k in range(self.n):if not T[k]:a=[k]T[k]=Truev=p[k]while v!=k:T[v]=Truea.append(v)v=p[v]if mode or len(a)>=2:A.append(a)return Adef 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 gcdif mod==None:x=1for m in self.cycle_division():g=gcd(x,len(m))x=(x//g)*len(m)return xelse:def factor(n):e=(n&(-n)).bit_length()-1yield 2,en>>=ep=3while p*p<=n:if n%p==0:e=0while n%p==0:n//=pe+=1yield p,ep+=2if n>1:yield n,1returnT={}for m in self.cycle_division():for p,e in factor(len(m)):T[p]=max(T.get(p,0), e)x=1for p in T:x*=pow(p, T[p], mod)x%=modreturn xdef 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]breakx=self.p[:i-1]y.sort()for j,b in enumerate(y):if a<b:x.append(b)del y[j]breakreturn 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 defaultdictif len(A)!=len(B):return defaultN=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,negN=int(input())P=[0]+list(map(int,input().split()))Mod=998244353B=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%=ModB.update(P[i],0)return X#==================================================print(solve())