Pentiment：比较 EZ 的线段树优化，但是我调了两天才调完 /ll。
不难想出一个暴力 DP：\(dp_{i,j}\) 表示直角蛇在第 \(i\) 行第 \(j\) 列进入第 \(i+1\) 行的方案数。然后转移是显然的：
- 当这个格子被 ban，\(dp_{i,j} = 0\)。
- 否则，\(dp_{i,j}\xleftarrow[l < k < r]{+} \sum dp_{i - 1, k}\)。
时间复杂度是 \(O(nm)\) 的，无法通过。
注意到 DP 转移的形式是一个区间覆盖，区间查询和的形式，所以直接上线段树转移即可。注意要特判空白行。
因为值域较大，所以可以离散化或者动态开点。时间复杂度 \(O(n\log n)\)。
本题还存在线性做法，区间覆盖可以上珂朵莉树，快速幂可以使用光速幂代替，时间复杂度 \(O(n)\)。但我不会光速幂，于是下面的代码是采用离散化线段树实现的。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 200005;
const ll mod = 998244353;
ll n, m, q, x[N], y[N], b[N], bn;
map<int, vector<int> > tot;
struct Node{int l, r;ll len, sm, tag = -1;
};
struct Segtree{Node tr[4 * N];void pushup(int p){tr[p].sm = (tr[lc].sm + tr[rc].sm) % mod;}void pushdown(int p){if(tr[p].tag != -1){tr[lc].sm = tr[lc].len * tr[p].tag % mod;tr[rc].sm = tr[rc].len * tr[p].tag % mod;tr[lc].tag = tr[p].tag;tr[rc].tag = tr[p].tag;}tr[p].tag = -1;}void build(int p, int ln, int rn){tr[p] = {ln, rn, (b[rn + 1] - b[ln]) % mod, (b[rn + 1] - b[ln]) % mod, -1};if(ln == rn) return;int mid = (ln + rn) >> 1;build(lc, ln, mid);build(rc, mid + 1, rn);pushup(p);}void update(int p, int ln, int rn, ll v){if(ln <= tr[p].l && tr[p].r <= rn){tr[p].sm = v * tr[p].len % mod;tr[p].tag = v;return;}pushdown(p);int mid = (tr[p].l + tr[p].r) >> 1;if(ln <= mid) update(lc, ln, rn, v);if(rn >= mid + 1) update(rc, ln, rn, v);pushup(p);}ll query(int p, int ln, int rn){if(ln <= tr[p].l && tr[p].r <= rn) return tr[p].sm;pushdown(p);int mid = (tr[p].l + tr[p].r) >> 1;if(rn <= mid) return query(lc, ln, rn);if(ln >= mid + 1) return query(rc, ln, rn);return (query(lc, ln, rn) + query(rc, ln, rn)) % mod;}
}tr1;
int getid(int x)
{return (lower_bound(b + 1, b + bn + 1, x) - b);
}
ll qpow(ll a, ll b)
{ll res = 1;while(b){if(b & 1) res = (res * a) % mod;b >>= 1;a = (a * a) % mod;}return res;
}
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> q;for(int i = 1; i <= q; i++){cin >> x[i] >> y[i];b[++bn] = y[i];b[++bn] = y[i] + 1;}b[++bn] = m + 1;b[++bn] = 1;sort(b + 1, b + bn + 1);bn = unique(b + 1, b + bn + 1) - b - 2;if(q == 0){cout << qpow(m, n + 1);return 0;}tr1.build(1, 1, bn);for(int i = 1; i <= q; i++)tot[x[i]].push_back(getid(y[i]));int pre = 0;for(auto itm : tot){int now = itm.fi;if(pre != now - 1){ll tmp = tr1.query(1, 1, bn);tmp = qpow(m, now - 2 - pre) * tmp % mod;tr1.update(1, 1, bn, tmp);}int nxt = 0;for(auto id : itm.se){if(nxt + 1 <= id - 1)tr1.update(1, nxt + 1, id - 1, tr1.query(1, nxt + 1, id - 1) * (now >= 0 ? 1 : b[id - 1] - b[nxt]) % mod);tr1.update(1, id, id, 0);nxt = id;}if(nxt + 1 <= bn)tr1.update(1, nxt + 1, bn, tr1.query(1, nxt + 1, bn) * (now >= 0 ? 1 : m - b[nxt]) % mod);pre = now;}ll ans = tr1.query(1, 1, bn);ans = qpow(m, n - pre) * ans % mod;cout << ans;return 0;
}