結果

問題 No.2230 Good Omen of White Lotus
コンテスト
ユーザー もろこし
提出日時 2025-10-03 16:04:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,664 ms / 2,000 ms
コード長 2,337 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 114,364 KB
最終ジャッジ日時 2025-10-03 16:05:02
合計ジャッジ時間 29,125 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
def ii(): return int(input())
def mi(d=0): return map(lambda x:int(x)-d,input().split())
INF = float("inf")
MOD = 998244353
def answer(s):
  print(s)
  exit()
def cross(xy):
  x,y = xy
  return (x+1,y),(x-1,y),(x,y+1),(x,y-1)
################################################
class SegTree:
  def __init__(self,n,inf,order,arr):
    self.inf = inf
    self.order = order
    self.bitlen = 2**n.bit_length()
    self.len = n
    self.n = self.bitlen*2-1
    arr += [inf]*(self.bitlen - n)
    self.arr = [None]*(self.bitlen-1) + arr

    def PreProcessing(index):
      if self.arr[index] == None:
        self.arr[index] = self.order(PreProcessing(2*index+1),PreProcessing(2*index+2))
      return self.arr[index]
    PreProcessing(0)
  
  #データ更新:index番目をxに変更
  def Renew(self,index,x):
    i = self.n - self.bitlen + index
    self.arr[i] = x
    while i != 0:
      i = (i-1)//2
      result = self.order(self.arr[i*2+1],self.arr[i*2+2])
      if result != self.arr[i]:
        self.arr[i] = result
  
  #index番目の値に+add
  def Add(self,index,add):
    i = self.n - self.bitlen + index
    self.arr[i] += add
    while i != 0:
      i = (i-1)//2
      self.arr[i] += add

  #[x,y)の範囲の結果を取得
  def GetRange(self,x,y,k=0,l=0,r=-1):
    if r == -1:
      r = self.bitlen
    if y<=l or r<=x:
      return self.inf
    elif x<=l and r<=y:
      return self.arr[k]
    else:
      return self.order(
        self.GetRange(x,y,2*k+1,l,(l+r)//2),
        self.GetRange(x,y,2*k+2,(l+r)//2,r)
        )
h,w,n,p = mi()
x_y = [[] for _ in range(h)]
for _ in range(n):
  x,y = mi()
  x_y[x-1].append(y)

dp = SegTree(w,0,max,[0]*w)
for hi in range(h):
  x_y[hi].sort()
  for y in x_y[hi]:
    dp.Renew(y-1,dp.GetRange(0,y)+1)
  # print(dp.arr[-dp.bitlen:])
t = dp.arr[0]
# print(t)

move = h+w-3
p1 = p-1
p2 = p-2
g = pow(p,-1,MOD)
ans = 1
for b in range((move).bit_length()):
  if move-t>>b & 1:
    ans = (ans*p1) % MOD

  if t>>b & 1:
    ans = (ans*p2)%MOD

  if move>>b & 1:
    ans = (ans*g) % MOD

  p1 = p1**2 % MOD
  p2 = p2**2 % MOD
  g = g**2 % MOD

print((1-ans)%MOD)

# q = ((p-1)**(move-t)%MOD * (p-2)**t%MOD)*pow(p,-move,MOD) %MOD
# print((1-q)%MOD)
0