結果
問題 | No.2230 Good Omen of White Lotus |
ユーザー |
|
提出日時 | 2023-02-24 21:54:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 3,985 bytes |
コンパイル時間 | 2,208 ms |
コンパイル使用メモリ | 203,640 KB |
最終ジャッジ日時 | 2025-02-10 20:56:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
#include <bits/stdc++.h>using i64 = long long;template<class T>constexpr T power(T a, i64 b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;}template<int P>struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(i64 x) : x{norm(x % P)} {}constexpr int norm(int x) const {if (x < 0) {x += P;}if (x >= P) {x -= P;}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(P - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, P - 2);}constexpr MInt &operator*=(MInt rhs) {x = 1LL * x * rhs.x % P;return *this;}constexpr MInt &operator+=(MInt rhs) {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {i64 v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}};template<int V, int P>constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P = 998244353;using Z = MInt<P>;template <typename T>struct Fenwick {int n;std::vector<T> a;Fenwick(int n = 0) {init(n);}void init(int n) {this->n = n;a.assign(n, T());}void add(int x, T v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] += v;}}T sum(int x) {auto ans = T();for (int i = x; i > 0; i -= i & -i) {ans += a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int kth(T k) {int x = 0;for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && k >= a[x + i - 1]) {x += i;k -= a[x - 1];}}return x;}};struct Max {int x = 0;Max &operator+=(Max a) & {if (a.x > x) {x = a.x;}return *this;}};int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int H, W, N;Z p;std::cin >> H >> W >> N >> p;p = 1 / p;std::vector<std::pair<int, int>> a(N);for (int i = 0; i < N; i++) {int x, y;std::cin >> x >> y;x--, y--;a[i] = {x, y};}std::sort(a.begin(), a.end());Fenwick<Max> fen(W);int cnt = 0;for (auto [x, y] : a) {int f = 1 + fen.sum(y + 1).x;fen.add(y, {f});cnt = std::max(cnt, f);}Z ans = 1 - power(1 - 2 * p, cnt) * power(1 - p, H + W - 3 - cnt);std::cout << ans << "\n";return 0;}