結果
| 問題 | No.2336 Do you like typical problems? |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-06-03 19:48:49 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,268 bytes |
| コンパイル時間 | 354 ms |
| コンパイル使用メモリ | 86,860 KB |
| 実行使用メモリ | 187,320 KB |
| 最終ジャッジ日時 | 2023-08-28 08:02:53 |
| 合計ジャッジ時間 | 15,724 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | AC | 88 ms
71,744 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | AC | 628 ms
148,684 KB |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
ソースコード
#yukicoder391C
'''
この問題は簡単すぎたので（迫真） はやくこれになりたい
うそです 解いたことありました
設問が難解 これがyukicoder
なるほど順列か Li,Riを順列に差し替えるのか
そして差し替え規則は一定、と。なんとなく理解してきた。
つまり(B1,C1), ... ,(Bn,Cn)を順列通りに並び替えるから、転倒数の総和を数えろ。
って問題になるわけだ。
より簡単な問題から考察しよう。
数字を範囲ではなく固定値として扱う場合は？
■AfterContest
Dに注力する判断は正しかった、と思う。Cも解こうか。
各数字ごとに転倒への寄与を考えたいところではある。
実装地獄になったんですけど･･･
SegTreeとLazySegTreeの2本を生やして殴る、ほんとうにこれでいいんですか
一旦ライブラリを貼る。
'''
#Segment Tree: O(logN)
class SegmentTree: # Segment Tree
def __init__(self,n,identity_e,combine_f): # 適応条件: 単位元eがある、互換可能
self._n=n; self._size=1 # モノイド(単位元)の例:
while self._size<self._n:self._size<<=1 # 足し算 0, かけ算 1, 最小 INF,
self._identity_e=identity_e # 最大 -INF, LCM(最小公倍数) 1
self._combine_f=combine_f #
self._node=[self._identity_e]*2*self._size # combine_f には関数を指定する
# def文で関数を自作してもいいし、
def build(self,array): # from operator import xor
assert len(array)==self._n,'array too large' # のようにimportしてもよい
for i,v in enumerate(array,start=self._size): #
self._node[i]=v # build: セグ木を建てる
for i in range(self._size-1,0,-1): # 異常時はassert関数でエラーを報告
self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
#
def update(self,index,value): # update: 一点更新 O(logN)
i=self._size+index; self._node[i]=value # 地点i(0-indexed)を更新する
while i-1: # 同時に上位のセグメントも更新する
i>>=1 #
self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
#
def fold(self,L,R): # fold: 区間取得 O(logN)
L+=self._size; R+=self._size # 区間 [L,R) の特定値を取得する
vL,vR=[self._identity_e]*2 #
while L<R: # nodeの遷移の考え方
if L&1: # ---1--- L: 自身より右の最小
vL=self._combine_f(vL,self._node[L]) # -2- -3- R: 自身-1より左の最小
L+=1 # 4 5 6 7 Rは計算より先に-1の
if R&1: # 処理をする点に注意
R-=1 # R---1---L
vR=self._combine_f(self._node[R],vR) # R-2- LLL. 例: L=6, R=5
L>>=1; R>>=1 # .R.5 L 7 Rの移動が変則的
return self._combine_f(vL,vR) # ←R L→
'''
値xにおいて、x未満を取る値がいくつあるか？で転倒数への寄与を計算する。
Ei: Aiがx未満になる期待値
Fi: Aiが丁度xになる期待値
とすると、Ai,Ajが転倒する期待値は
Fi * Ej * NP2 * (N-2)! : Aiが丁度xを取り、Ajがx未満を取る。それ以外の順番は不定
となる。あとはこれをベースに式を圧縮する。
L=x となる半開区間[L,L+d)において、答えへの寄与度を計算する。
W: 区間数: この閉区間内で、Ai=xとなるAiの個数
X: sum(Fi): 丁度Ai=xとなる期待値の総和
Y: sum(Fi*Ei): Ai=xを取るAiについて、Ai<xとなる期待値の積を求め、その値の総和
Z: sum(Ei): Aiがx未満となる期待値の総和
とすると、寄与は
(-X*W* d*(d+1)*(2*d+1)//6 + ((3*X-Y)*W-X*Z)* d*(d+1)//2 +(2*X-Y)*(Z-W)* d ) * nP2 * (N-2)!
と求められる。この総和をN! 倍すれば答えになる、はず。
'''
import sys
from collections import defaultdict as dd
add=lambda x,y:x+y
f=lambda:list(map(int,input().split()))
#入力受取 Dで座標圧縮
N=int(input()); MOD=998244353; Task=[f() for _ in range(N)]; D=dd(list)
for i,(b,c) in enumerate(Task): D[b].append((i,0)); D[c+1].append((i,1))
if N==1: print(0); sys.exit()
#計算の前準備 区間長の逆元、逆元の2乗値、階乗を求める
Unit1=[pow(Task[i][1]-Task[i][0]+1,MOD-2,MOD) for i in range(N)]
Unit2=[Unit1[i]**2%MOD for i in range(N)]; fact=[1]*(N+1)
for i in range(1,N+1): fact[i]=fact[i-1]*i%MOD
#SegTree: 現在区間内にあるAiに対して、Fiの総和とFi^2の総和を求める
ST1=SegmentTree(N,0,add); ST2=SegmentTree(N,0,add)
#定数項を diff * nP2 * (N-2)! で算出可能にしておく。diff以外は最後にまとめて乗算。
diff=lambda W,X,Y,Z,d:-X*W*d*(d+1)*(2*d+1)//6+((3*X-Y)*W-X*Z)*d*(d+1)//2+(2*X-Y)*(Z-W)*d
P=sorted(D.keys()); sumX,sumY,sumZ,sumW,ans=0,0,0,0,0
for index,key in enumerate(P):
if index:
#答えを更新
d=P[index]-P[index-1]; ans+=diff(sumW,sumX,sumY,sumZ,d); ans%=MOD
#dが移動したぶんのパラメータを更新
sumZ+=sumX*d; sumZ%=MOD; sumY+=ST2.fold(0,N)*d; sumY%=MOD
#区間進入時のクエリを処理 t=0が追加クエリ、t=1が削除クエリ
for i,t in D[key]:
if t==0: ST1.update(i,Unit1[i]); ST2.update(i,Unit2[i]); sumW+=1
if t==1: ST1.update(i,0); ST2.update(i,0); sumW-=1; sumY-=Unit1[i]
#各種パラメータを更新
sumX=ST1.fold(0,N)%MOD
#回答
print(ans*N*(N-1)%MOD*fact[N-2]%MOD*fact[N]%MOD)