結果
問題 | No.2230 Good Omen of White Lotus |
ユーザー |
|
提出日時 | 2023-02-25 00:09:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 143 ms / 2,000 ms |
コード長 | 16,647 bytes |
コンパイル時間 | 1,783 ms |
コンパイル使用メモリ | 147,732 KB |
最終ジャッジ日時 | 2025-02-10 22:55:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
#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_classusing 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 = cstruct 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 + 1) % 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};}