#![allow(unused)] #![allow(non_snake_case)] #![allow(dead_code)] type Mint = ModInt998244353; struct Additive; impl Monoid for Additive{ type S = Mint; fn identity() -> Self::S {Mint::new(0)} fn binary_operation(&a: &Self::S, &b: &Self::S) -> Self::S {a+b} } struct MulAdd; impl MapMonoid for MulAdd{ type M = Additive; type F = Mint; fn identity_map() -> Self::F {Mint::new(1)} fn mapping(&f: &Self::F, &a: &::S) -> ::S {f*a} fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {f*g} } use proconio::input; fn main(){ input!{ N:usize, mut Point: [(i64,i64);N], } assert!(1 <= N && N <= 200000); for &(x,y) in Point.iter(){ assert!(-1_000_000_000 <= x && x <= 1_000_000_000); assert!(-1_000_000_000 <= y && y <= 1_000_000_000); } let mut ans = Mint::new(0); //x座標 Point.sort_by_key(|&(x,y)| x); //rank[i]:Point[i]が上から何番目の点か let mut yi = vec![]; for i in 0..N{ yi.push((Point[i].1,i)); } yi.sort(); yi.reverse(); let mut rank = vec![0usize;N]; for r in 0..N{ rank[yi[r].1] = r; } //prob[i]: 左ゾーンで一番下の「がrank[i]の点かつ,対応する」が存在しない確率 let mut prob = LazySegtree::::new(N+3); for i in 0..N{ prob.set(i,(Mint::new(1)/Mint::new(4))*(Mint::new(3)/Mint::new(4)).pow(i as u64)); } for i in (1..N).rev(){ prob.apply_range(0..rank[i],Mint::new(3)/Mint::new(4)); prob.set(rank[i],Mint::new(0)); prob.apply_range(rank[i]+1..N,Mint::new(4)/Mint::new(3)); ans += Mint::new(Point[i].0-Point[i-1].0)*(Mint::new(1)-prob.prod(0..N)-(Mint::new(3)/Mint::new(4)).pow(i as u64)) } //y座標 Point.sort_by_key(|&(x,y)| y); //rank[i]:Point[i]が右から何番目の点か let mut xi = vec![]; for i in 0..N{ xi.push((Point[i].0,i)); } xi.sort(); xi.reverse(); let mut rank = vec![0usize;N]; for r in 0..N{ rank[xi[r].1] = r; } //prob[i]: 下ゾーンで一番左の」がrank[i]の点かつ,対応する「が存在しない確率 let mut prob = LazySegtree::::new(N+3); for i in 0..N{ prob.set(i,(Mint::new(1)/Mint::new(4))*(Mint::new(3)/Mint::new(4)).pow(i as u64)); } for i in (1..N).rev(){ prob.apply_range(0..rank[i],Mint::new(3)/Mint::new(4)); prob.set(rank[i],Mint::new(0)); prob.apply_range(rank[i]+1..N,Mint::new(4)/Mint::new(3)); ans += Mint::new(Point[i].1-Point[i-1].1)*(Mint::new(1)-prob.prod(0..N)-(Mint::new(3)/Mint::new(4)).pow(i as u64)) } ans *= Mint::new(4).pow(N as u64); ans *= Mint::new(2); println!("{}",ans); } //ac-library-rs use std::ops::*; use std::fmt; #[derive(Copy, Clone, Eq, PartialEq, Default, Hash, Debug)] pub struct ModInt998244353(u32); impl ModInt998244353 { pub const MOD: u32 = 998_244_353; pub fn new>(v: T) -> Self { let m = Self::MOD as i128; let mut x = v.into() % m; if x < 0 { x += m; } Self(x as u32) } pub fn raw(v: u32) -> Self { debug_assert!(v < Self::MOD); Self(v) } pub fn val(self) -> u32 { self.0 } pub fn pow(self, mut e: u64) -> Self { let mut base = self; let mut res = Self::raw(1); while e > 0 { if e & 1 == 1 { res *= base; } base *= base; e >>= 1; } res } pub fn inv(self) -> Self { self.pow((Self::MOD - 2) as u64) } } impl From for ModInt998244353 { fn from(v: i8) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: i16) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: i32) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: i64) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: u8) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: u16) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: u32) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: u64) -> Self { Self::new(v) } } impl From for ModInt998244353 { fn from(v: usize) -> Self { Self::new(v as i128) } } impl fmt::Display for ModInt998244353 { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.0) } } impl Add for ModInt998244353 { type Output = Self; fn add(self, rhs: Self) -> Self { let mut x = self.0 + rhs.0; if x >= Self::MOD { x -= Self::MOD; } Self(x) } } impl AddAssign for ModInt998244353 { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Sub for ModInt998244353 { type Output = Self; fn sub(self, rhs: Self) -> Self { let mut x = self.0.wrapping_sub(rhs.0); if x >= Self::MOD { x = x.wrapping_add(Self::MOD); } Self(x) } } impl SubAssign for ModInt998244353 { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl Mul for ModInt998244353 { type Output = Self; fn mul(self, rhs: Self) -> Self { Self(((self.0 as u64 * rhs.0 as u64) % Self::MOD as u64) as u32) } } impl MulAssign for ModInt998244353 { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl Div for ModInt998244353 { type Output = Self; fn div(self, rhs: Self) -> Self { self * rhs.inv() } } impl DivAssign for ModInt998244353 { fn div_assign(&mut self, rhs: Self) { *self = *self / rhs; } } impl Neg for ModInt998244353 { type Output = Self; fn neg(self) -> Self { if self.0 == 0 { self } else { Self(Self::MOD - self.0) } } } pub trait Monoid { type S: Clone; fn identity() -> Self::S; fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S; } fn ceil_pow2(n: usize) -> usize { let mut x = 0usize; while (1usize << x) < n { x += 1; } x } pub trait MapMonoid { type M: Monoid; type F: Clone; fn identity_element() -> ::S { Self::M::identity() } fn binary_operation( a: &::S, b: &::S, ) -> ::S { Self::M::binary_operation(a, b) } fn identity_map() -> Self::F; fn mapping(f: &Self::F, x: &::S) -> ::S; fn composition(f: &Self::F, g: &Self::F) -> Self::F; } #[derive(Clone)] pub struct LazySegtree { n: usize, size: usize, log: usize, d: Vec<::S>, lz: Vec, } impl Default for LazySegtree { fn default() -> Self { Self::new(0) } } impl LazySegtree { pub fn new(n: usize) -> Self { vec![F::identity_element(); n].into() } pub fn len(&self) -> usize { self.n } pub fn is_empty(&self) -> bool { self.n == 0 } pub fn set(&mut self, mut p: usize, x: ::S) { assert!(p < self.n); p += self.size; for i in (1..=self.log).rev() { self.push(p >> i); } self.d[p] = x; for i in 1..=self.log { self.update(p >> i); } } pub fn get(&mut self, mut p: usize) -> ::S { assert!(p < self.n); p += self.size; for i in (1..=self.log).rev() { self.push(p >> i); } self.d[p].clone() } pub fn prod(&mut self, range: R) -> ::S where R: RangeBounds, { if range.start_bound() == Bound::Unbounded && range.end_bound() == Bound::Unbounded { return self.all_prod(); } let mut r = match range.end_bound() { Bound::Included(r) => *r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let mut l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => *l + 1, Bound::Unbounded => 0, }; assert!(l <= r && r <= self.n); if l == r { return F::identity_element(); } l += self.size; r += self.size; for i in (1..=self.log).rev() { if ((l >> i) << i) != l { self.push(l >> i); } if ((r >> i) << i) != r { self.push((r - 1) >> i); } } let mut sml = F::identity_element(); let mut smr = F::identity_element(); while l < r { if l & 1 != 0 { sml = F::binary_operation(&sml, &self.d[l]); l += 1; } if r & 1 != 0 { r -= 1; smr = F::binary_operation(&self.d[r], &smr); } l >>= 1; r >>= 1; } F::binary_operation(&sml, &smr) } pub fn all_prod(&self) -> ::S { self.d[1].clone() } pub fn apply(&mut self, mut p: usize, f: F::F) { assert!(p < self.n); p += self.size; for i in (1..=self.log).rev() { self.push(p >> i); } self.d[p] = F::mapping(&f, &self.d[p]); for i in 1..=self.log { self.update(p >> i); } } pub fn apply_range(&mut self, range: R, f: F::F) where R: RangeBounds, { let mut r = match range.end_bound() { Bound::Included(r) => *r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let mut l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => *l + 1, Bound::Unbounded => 0, }; assert!(l <= r && r <= self.n); if l == r { return; } l += self.size; r += self.size; for i in (1..=self.log).rev() { if ((l >> i) << i) != l { self.push(l >> i); } if ((r >> i) << i) != r { self.push((r - 1) >> i); } } let l2 = l; let r2 = r; while l < r { if l & 1 != 0 { self.all_apply(l, f.clone()); l += 1; } if r & 1 != 0 { r -= 1; self.all_apply(r, f.clone()); } l >>= 1; r >>= 1; } l = l2; r = r2; for i in 1..=self.log { if ((l >> i) << i) != l { self.update(l >> i); } if ((r >> i) << i) != r { self.update((r - 1) >> i); } } } pub fn max_right(&mut self, mut l: usize, g: G) -> usize where G: Fn(::S) -> bool, { assert!(l <= self.n); assert!(g(F::identity_element())); if l == self.n { return self.n; } l += self.size; for i in (1..=self.log).rev() { self.push(l >> i); } let mut sm = F::identity_element(); loop { while l % 2 == 0 { l >>= 1; } let nxt = F::binary_operation(&sm, &self.d[l]); if !g(nxt.clone()) { while l < self.size { self.push(l); l *= 2; let nxt = F::binary_operation(&sm, &self.d[l]); if g(nxt.clone()) { sm = nxt; l += 1; } } return l - self.size; } sm = nxt; l += 1; if l & l.wrapping_neg() == l { break; } } self.n } pub fn min_left(&mut self, mut r: usize, g: G) -> usize where G: Fn(::S) -> bool, { assert!(r <= self.n); assert!(g(F::identity_element())); if r == 0 { return 0; } r += self.size; for i in (1..=self.log).rev() { self.push((r - 1) >> i); } let mut sm = F::identity_element(); loop { r -= 1; while r > 1 && r % 2 == 1 { r >>= 1; } let nxt = F::binary_operation(&self.d[r], &sm); if !g(nxt.clone()) { while r < self.size { self.push(r); r = 2 * r + 1; let nxt = F::binary_operation(&self.d[r], &sm); if g(nxt.clone()) { sm = nxt; r -= 1; } } return r + 1 - self.size; } sm = nxt; if r & r.wrapping_neg() == r { break; } } 0 } fn update(&mut self, k: usize) { self.d[k] = F::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]); } fn all_apply(&mut self, k: usize, f: F::F) { self.d[k] = F::mapping(&f, &self.d[k]); if k < self.size { self.lz[k] = F::composition(&f, &self.lz[k]); } } fn push(&mut self, k: usize) { let f = self.lz[k].clone(); self.all_apply(2 * k, f.clone()); self.all_apply(2 * k + 1, f); self.lz[k] = F::identity_map(); } } impl From::S>> for LazySegtree { fn from(v: Vec<::S>) -> Self { let n = v.len(); let log = ceil_pow2(n); let size = 1 << log; let mut d = vec![F::identity_element(); 2 * size]; let lz = vec![F::identity_map(); size]; d[size..(size + n)].clone_from_slice(&v); let mut ret = Self { n, size, log, d, lz }; for i in (1..size).rev() { ret.update(i); } ret } }