結果
問題 | No.2230 Good Omen of White Lotus |
ユーザー | Carpenters-Cat |
提出日時 | 2023-02-25 00:07:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 16,643 bytes |
コンパイル時間 | 2,406 ms |
コンパイル使用メモリ | 153,052 KB |
実行使用メモリ | 8,200 KB |
最終ジャッジ日時 | 2024-09-13 06:18:14 |
合計ジャッジ時間 | 6,721 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
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 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <utility> #include <vector> // def_class using namespace std; using ll = long long; using Vi = vector<int>; using VVi = vector<Vi>; using Vl = vector<ll>; using VVl = vector<Vl>; using Pii = pair<int, int>; using Vp = vector<Pii>; using VVp = vector<Vp>; using Pl = pair<ll, int>; using Vpl = vector<Pl>; using VVpl = vector<Vpl>; using tup = tuple<ll, ll, int>; using Vt = vector<tuple<int, int, int>>; using Pll = pair<ll, ll>; using Vc = vector<char>; using VVc = vector<Vc>; template <class U> using PQmax = priority_queue<U>; template <class U> using PQmin = priority_queue<U, vector<U>, greater<U>>; // func_def // 再帰で計算するトポロジカルソート void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par); void tprsort(int u, const VVpl& gr, Vi& tpr, Vi& par); // キューで計算するトポロジカルソート void tprsort(const VVi& gr, Vi& tpr); ll mpow(ll x, ll n, ll m = 1e9 + 7); ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m = 1e9 + 7); ll gcd(ll a, ll b); int LCA(const VVi& par, const Vi& depth, int a, int b); Vi sccResolve(const VVi& gr); void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s); void dijkstra_prev(const VVi& gr, const VVl& cost, Vl& dist, Vi& prev, int s); // ax + by = c struct DLine { ll a; ll b; ll c; bool operator<(const DLine l) const; }; DLine make_dline(ll x1, ll y1, ll x2, ll y2); double calc_tilt(DLine l1); bool is_upper(DLine l, ll x, ll y); bool is_inside(DLine l, ll x, ll y); class unionfind { private: Vi par; Vi siz; public: unionfind(int N); unionfind(); int root(int v); void merge(int a, int b); bool same(int a, int b); int size(int a); }; class w_unionfind { private: Vi par; Vi siz; Vl val; Vi val2; ll H; Vl ex_val; public: w_unionfind(int N, int H = 0); w_unionfind(); int root(int v); bool merge(int a, int b, int z); bool same(int a, int b); int value(int a); void cr_val(int a, ll ex) { ex_val[a] = ex; } bool is_cr(int a) { return ex_val[a] >= 0; } }; class BIT { private: Vl bit; int siz; public: BIT(int N); BIT(); ll& get(int id); void add(int id, ll a, ll m); ll sum(int id, ll m); }; class RMQ { private: Vl val; int siz; ll e; ll prod_sub(int l, int r, int a, int b, int id); public: RMQ(int N, ll e = (ll)1e18); RMQ(Vl A, ll e = (ll)1e18); RMQ(ll e = (ll)1e18); ll& get(int id); void set(int id, ll a); void add(int id, ll a); ll prod(int l, int r); }; class Fraction { public: ll mot; ll son; // a/b を生成 Fraction(ll a = 0, ll b = 1) { ll g = gcd(abs(a), abs(b)); if (b < 0) { a *= -1; b *= -1; } mot = b / g; son = a / g; } Fraction(const Fraction& F) : mot(F.mot), son(F.son) {} Fraction operator+(const Fraction A) const; Fraction operator-(const Fraction A) const; Fraction operator*(const Fraction A) const; // Fraction operator/(const int& a); Fraction operator/(const Fraction A) const; Fraction operator=(const Fraction& A); bool operator<(const Fraction A) const; bool operator>(const Fraction A) const; }; void chmax(ll& a, ll b) { if (a < b) { a = b; } } int calc_LIS(const Vi& X) { int N = X.size(); Vi dp(N, 1e9 + 7); for (auto x : X) { int& pt = *(upper_bound(dp.begin(), dp.end(), x)); pt = x; } int fl = 0; while (fl < N && dp[fl] < 1e9 + 7) { fl++; } return fl; } // sの部分木のsizeを返す int dfs_hld(const VVi& gr, Vi& hld_son, Vi& hld_id, Vi& hld_root, int s, int p = -1) { hld_son[s] = -1; int ma = 0; int siz = 1; for (auto v : gr[s]) { if (v == p) { continue; } int n = dfs_hld(gr, hld_son, hld_id, hld_root, v, s); siz += n; if (ma < n) { ma = n; hld_son[s] = v; } } return siz; } void hld_b(const VVi& gr, Vi& hld_son, Vi& hld_id, Vi& hld_root, Vi& hld_num, int s, int p = -1) { for (auto v : gr[s]) { if (v == p) { continue; } if (v != hld_son[s]) { hld_id[v] = hld_root.size(); hld_root.push_back(v); hld_num[v] = 0; } else { hld_id[v] = hld_id[s]; hld_num[v] = hld_num[s] + 1; } hld_b(gr, hld_son, hld_id, hld_root, hld_num, v, s); } } void HLD(const VVi& gr, Vi& hld_son, Vi& hld_id, Vi& hld_root, Vi& hld_num, int s = 0) { hld_son.assign(gr.size(), -1); hld_id.resize(gr.size()); hld_num.resize(gr.size()); dfs_hld(gr, hld_son, hld_id, hld_root, s); hld_root.push_back(s); hld_id[s] = 0; hld_num[s] = 0; hld_b(gr, hld_son, hld_id, hld_root, hld_num, s); } int dfs(const VVi& gr, Vi& vis, int s) { int r = 1; vis[s] = 1; for (auto v : gr[s]) { if (vis[v]) { continue; } r += dfs(gr, vis, v); if (r >= 1000000) { return 1000000; } } vis[s] = 0; return r; } ll const m = 998244353; int main () { ll H, W, N, P; cin >> H >> W >> N >> P; ll Q = mpow(P, m - 2, m); Vpl A(N); for (auto& [a, b] : A) { cin >> a >> b; } sort(A.begin(), A.end()); Vi X; for (auto [a, b] : A) { X.push_back(b); } int n = calc_LIS(X); ll ans = mpow(P - 2, n, m); ans *= mpow(P - 1, H + W - 3 - n, m); ans %= m; /*if (!((H + W) & 1)) { ans = m - ans; ans %= m; }*/ // cout << ans << endl; ans *= mpow(Q, H + W - 3, m); ans %= m; cout << (m - ans) % m << endl; } // 再帰型 void tprsort(int u, const VVi& gr, Vi& tpr, Vi& par) { // idx[u] = tpr.size(); /*for (int v : gr[u]) { if (par[v] == u || par[v] == -1) { par[v] = u; tprsort(v, gr, tpr, par); } } tpr.push_back(u);*/ stack<int> st; st.push(u); bool vis[2000020]; par.assign(gr.size(), -1); par[u] = -2; tpr.clear(); for (int i = 0; i <= gr.size(); i++) { vis[i] = false; } while (!st.empty()) { int v = st.top(); if (!vis[v]) { vis[v] = true; for (int p : gr[v]) { if (par[p] == -1) { par[p] = v; st.push(p); } } } else { tpr.push_back(v); st.pop(); } } } Vi sccResolve(const VVi& gr) { int N = gr.size(); Vi tpr; Vi par(N, -1); for (int i = 0; i < N; i++) { if (par[i] == -1) { tprsort(i, gr, tpr, par); } } Vi ret(N, -1); int now = 0; for (int i = N - 1; i >= 0; i--) { int u = tpr[i]; if (ret[u] != -1) { continue; } ret[u] = now; stack<int> st; st.push(u); while (!st.empty()) { int v = st.top(); st.pop(); for (int p : gr[v]) { if (ret[p] == -1) { st.push(p); ret[p] = now; } } } now++; } return ret; } ll gcd(ll a, ll b) { while (b) { a %= b; swap(a, b); } return a; } ll mpow(ll x, ll n, ll m) { ll ret = 1; while (n) { if (n % 2) { ret *= x; ret %= m; } x = (x * x) % m; n /= 2; } return ret; } ll comb(int n, int r, const Vl& kai, const Vl& fkai, ll m) { if (n < 0 || r < 0 || n < r) { return 0; } ll ret = kai[n]; ret *= fkai[r]; ret %= m; ret *= fkai[n - r]; ret %= m; return ret; } int LCA(const VVi& par, const Vi& depth, int a, int b) { if (depth[a] < depth[b]) { swap(a, b); } int dis = depth[a] - depth[b]; for (int i = 19; i >= 0; i--) { if ((dis >> i) & 1) { a = par[i][a]; } } if (a == b) { return a; } for (int i = 19; i >= 0; i--) { if (par[i][a] != par[i][b]) { a = par[i][a]; b = par[i][b]; } } return par[0][a]; } void dijkstra(const VVi& gr, const VVl& cost, Vl& dist, int s) { ll INF = (ll)1e18; dist.assign(gr.size(), INF); dist[s] = 0; PQmin<Pl> pque; pque.push(make_pair(0, s)); while (!pque.empty()) { auto [L, u] = pque.top(); pque.pop(); while (L != dist[u] && !pque.empty()) { tie(L, u) = pque.top(); pque.pop(); } for (int i = 0; i < gr[u].size(); i++) { int v = gr[u][i]; ll c = cost[u][i]; if (dist[v] > c + L) { dist[v] = c + L; pque.push(make_pair(dist[v], v)); } } } return; } void dijkstra_prev(const VVi& gr, const VVl& cost, Vl& dist, Vi& prev, int s) { ll INF = (ll)1e18; dist.assign(gr.size(), INF); dist[s] = 0; PQmin<Pl> pque; pque.push(make_pair(0, s)); while (!pque.empty()) { auto [L, u] = pque.top(); pque.pop(); while (L != dist[u] && !pque.empty()) { tie(L, u) = pque.top(); pque.pop(); } for (int i = 0; i < gr[u].size(); i++) { int v = gr[u][i]; ll c = cost[u][i]; if (dist[v] > c + L) { dist[v] = c + L; prev[v] = u; pque.push(make_pair(dist[v], v)); } } } return; } DLine make_dline(ll x1, ll y1, ll x2, ll y2) { ll dx = x1 - x2; ll dy = y2 - y1; if (dy < 0) { dx *= -1; dy *= -1; } if (dy == 0) { dx = abs(dx); } ll g = gcd(dy, abs(dx)); dx /= g; dy /= g; ll c = dx * y1 + dy * x1; return DLine{dy, dx, c}; } double calc_tilt(DLine l) { return atan2(l.a, l.b); } bool is_upper(DLine l, ll x, ll y) { return x * l.a + y * l.b > l.c; } bool is_inside(DLine l, ll x, ll y) { return x * l.a + y * l.b == l.c; } unionfind::unionfind(int N) { par.resize(N); siz.assign(N, 1); for (int i = 0; i < N; i++) { par[i] = i; } } unionfind::unionfind() { par.resize(100010); siz.assign(100010, 1); for (int i = 0; i <= 100010; i++) { par[i] = i; } } int unionfind::root(int v) { if (v == par[v]) { return v; } return par[v] = root(par[v]); } void unionfind::merge(int a, int b) { a = root(a); b = root(b); if (a == b) { return; } if (siz[a] < siz[b]) { int t = a; a = b; b = t; } par[b] = a; siz[a] += siz[b]; } bool unionfind::same(int a, int b) { a = root(a); b = root(b); return a == b; } int unionfind::size(int a) { return siz[this->root(a)]; } w_unionfind::w_unionfind(int N, int H) : H(H) { par.resize(N); siz.assign(N, 1); val.assign(N, 0); val2.assign(N, 1); ex_val.assign(N, -1); for (int i = 0; i < N; i++) { par[i] = i; } } w_unionfind::w_unionfind() { par.resize(100010); siz.assign(100010, 1); val.assign(100010, 0); for (int i = 0; i <= 100010; i++) { par[i] = i; } } int w_unionfind::root(int v) { if (v == par[v]) { return v; } int p = par[v]; int q = root(par[v]); val[v] += val2[v] * val[p]; val[v] += H; val[v] %= H; val2[v] *= val2[p]; if (ex_val[q] >= 0) { ex_val[v] = ex_val[q] * val2[v] + val[v]; ex_val[v] += H; ex_val[v] %= H; } return par[v] = q; } bool w_unionfind::merge(int a, int b, int z) { // z -= this->value(b); // z += this->value(a); int pa = root(a); int pb = root(b); if (ex_val[a] >= 0 && ex_val[b] >= 0) { return ((ex_val[a] + ex_val[b]) % H) == z; } if (pa == pb) { z += H - (val[a] - val[b]); z %= H; if (val2[a] == -1) { z = H - z; z %= H; } if (H % 2 == 0 && z % 2 == 1) { return false; } if (z % 2 == 0) { z /= 2; } else { z *= ((H + 1) / 2); } if (ex_val[pa] >= 0 && ex_val[pa] != z) { return false; } ex_val[pa] = z; return true; } if (siz[pa] < siz[pb]) { swap(pa, pb); swap(a, b); } if (ex_val[pb] >= 0) { swap(pa, pb); swap(a, b); } par[pb] = pa; siz[pa] += siz[pb]; val[pb] = (-val2[b]) * (val[a] + val[b] - z); val[pb] += H * 3; val[pb] %= H; val2[pb] *= (-val2[a]); return true; } bool w_unionfind::same(int a, int b) { a = root(a); b = root(b); return a == b; } int w_unionfind::value(int a) { root(a); return val[a]; } BIT::BIT(int N) { siz = N; bit.assign(N + 1, 0); } BIT::BIT() { siz = 0; } ll& BIT::get(int id) { return bit[id]; } void BIT::add(int id, ll a, ll m) { while (id <= siz) { bit[id] += a; if (m > 0) { bit[id] %= m; } id += (id & (-id)); } } ll BIT::sum(int id, ll m) { ll ret = 0; while (id) { ret += bit[id]; if (m > 0) { ret %= m; } id -= (id & (-id)); } return ret; } RMQ::RMQ(int N, ll e) { siz = 1; this->e = e; while (siz < N) { siz *= 2; } val.assign(siz * 2, e); } RMQ::RMQ(Vl A, ll e) { siz = 1; this->e = e; while (siz < A.size()) { siz *= 2; } val.assign(siz * 2, e); for (int i = 0; i < A.size(); i++) { val[i + siz - 1] = A[i]; } for (int i = siz - 2; i >= 0; i--) { int l = i * 2 + 1; int r = i * 2 + 2; val[i] = min(val[l], val[r]); } } RMQ::RMQ(ll e) { siz = (1 << 20); this->e = e; val.assign(siz * 2, e); } ll& RMQ::get(int id) { return val[id + siz - 1]; } void RMQ::set(int id, ll a) { id += siz - 1; val[id] = a; while (id > 0) { id = (id - 1) / 2; int l = id * 2 + 1; int r = id * 2 + 2; ll v = min(val[l], val[r]); /*if (val[id] == v) { break; }*/ val[id] = v; } } void RMQ::add(int id, ll a) { ll n = a + val[id + siz - 1]; this->set(id, n); } ll RMQ::prod_sub(int l, int r, int a, int b, int id) { if (b <= l || r <= a) { return this->e; } if (l <= a && b <= r) { return val[id]; } return min(this->prod_sub(l, r, a, (a + b) / 2, id * 2 + 1), this->prod_sub(l, r, (a + b) / 2, b, id * 2 + 2)); } ll RMQ::prod(int l, int r) { return prod_sub(l, r, 0, siz, 0); } Fraction Fraction::operator+(const Fraction A) const { return Fraction{this->son * A.mot + A.son * this->mot, this->mot * A.mot}; } Fraction Fraction::operator-(const Fraction A) const { return Fraction{this->son * A.mot - A.son * this->mot, this->mot * A.mot}; } Fraction Fraction::operator*(const Fraction A) const { return Fraction{this->son * A.son, this->mot * A.mot}; } // Fraction Fraction::operator/(const int& a) // { // return *this / (ll)a; // } Fraction Fraction::operator/(const Fraction A) const { return Fraction{this->son * A.mot, this->mot * A.son}; } Fraction Fraction::operator=(const Fraction& A) { this->mot = A.mot; this->son = A.son; return *this; } bool Fraction::operator<(const Fraction A) const { if (A.son < 0 && this->son > 0) { return false; } if (A.son > 0 && this->son < 0) { return true; } if (A.son < 0) { return (A * -1) < (*this * -1); } if (max({this->son, A.son, A.mot, this->mot}) < 3000000000ll) { return this->son * A.mot < this->mot * A.son; } else if (this->son / this->mot != A.son / A.mot) { return this->son / this->mot < A.son / A.mot; } else { ll f = this->son / this->mot; return (*this - f) < (A - f); } } bool Fraction::operator>(const Fraction A) const { return A < *this; } bool DLine::operator<(const DLine l) const { if (a == l.a && b == l.b) { return c < l.c; } return Fraction{a, -b} < Fraction{l.a, -l.b}; }