結果

問題 No.2230 Good Omen of White Lotus
ユーザー lam6er
提出日時 2025-03-31 17:30:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,043 ms / 2,000 ms
コード長 2,121 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 146,188 KB
最終ジャッジ日時 2025-03-31 17:31:10
合計ジャッジ時間 17,041 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 998244353

class FenwickTreeMax:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing

    def update(self, idx, value):
        # idx is 1-based
        while idx <= self.n:
            if self.tree[idx] < value:
                self.tree[idx] = value
            else:
                break  # no need to update further
            idx += idx & -idx

    def query(self, idx):
        # returns maximum in [1..idx]
        res = 0
        while idx > 0:
            if self.tree[idx] > res:
                res = self.tree[idx]
            idx -= idx & -idx
        return res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    H = int(data[ptr]); ptr +=1
    W = int(data[ptr]); ptr +=1
    N = int(data[ptr]); ptr +=1
    P = int(data[ptr]); ptr +=1

    good = []
    for _ in range(N):
        x = int(data[ptr]); ptr +=1
        y = int(data[ptr]); ptr +=1
        good.append( (x, y) )

    K = 0
    if N > 0:
        # Sort good news cells by x, then y
        good.sort(key=lambda p: (p[0], p[1]))
        # Compress y coordinates
        ys = list({p[1] for p in good})
        ys.sort()
        size_y = len(ys)
        ft = FenwickTreeMax(size_y)
        max_k = 0
        for x, y in good:
            idx = bisect.bisect_left(ys, y)
            pos = idx + 1  # 1-based
            current = ft.query(pos)
            new_val = current + 1
            # Update Fenwick tree
            ft.update(pos, new_val)
            if new_val > max_k:
                max_k = new_val
        K = max_k

    T = H + W - 3

    # Compute numerator and denominator
    numerator1 = pow(P-2, K, MOD) if (P != 2 or K ==0) else 0
    numerator2 = pow(P-1, T - K, MOD)
    numerator = (numerator1 * numerator2) % MOD
    denominator = pow(P, T, MOD)
    inv_denominator = pow(denominator, MOD-2, MOD)  # Fermat's little theorem
    product = (numerator * inv_denominator) % MOD
    ans = (1 - product) % MOD
    if ans < 0:
        ans += MOD
    print(ans)

if __name__ == "__main__":
    main()
0