Description

给定 \(n\times m\) 的矩阵，从第 \(1\) 行任意格子出发，每次向下、左、有走一步，有 \(q\) 个障碍不能经过，求走到第 \(n\) 行任意格子的方案。

对于所有数据，\(1\leq n,m\leq 10^9\)，\(1\leq q\leq 10^5\)。

link：https://www.luogu.com.cn/problem/P9221

Solution

算法一

考虑朴素 DP，设 \(f_{i,j}\) 是从第 \(1\) 行任意格子出发，走到 \((i,j)\) 的方案数。枚举行 \(i\) 进行 DP，令 \(x,y\) 分别为 \((i,j)\) 左边和右边的第一个障碍，\(l=x+1,r=y-1\)，则 \(\displaystyle f_{i,j}=\sum_{k=l}^{r}f_{i-1,k}\)。初值是对于所有 \(i\in[1,m]\)，\(f_{0,i}=1\)。

时间复杂度 \(\mathcal{O}(nm+q)\)，期望得分 \(25\)。

算法二

考虑优化算法一。对于每个 \([l,r]\)，\(j\) 在这之间的 \(f_{i,j}\) 都相等，令这个值为 \(k\)。考虑珂朵莉树（颜色段均摊），将三元组 \((l,r,k)\) 放入容器进行操作。由于每次遍历上行的所有区间，所以放入 vector 即可。每次转移时使用双指针维护区间的和。

时间复杂度 \(\mathcal{O}(n+q)\)，期望得分 \(45\)。

算法三

考虑 \(q=0\) 的部分分。\(q=0\) 即每行都是 \(l=1,r=m\)。观察转移方程可知答案为 \(m^{n+1}\)。

时间复杂度 \(\mathcal{O}(\log n)\)，期望得分 \(10\)。

算法四

对有障碍的行跑算法二，没有障碍的行跑算法三即可。算法三有些改动，设当前行（有障碍）为 \(i\)，上一行有障碍的是 \(p\) 且 \(p<i-1\)，可以将上一行直接处理为 \(\displaystyle(1,m,m^{i-p-2}\times\sum_{j=1}^{m}f_{p,j})\)。需要特判没有做到第 \(n\) 行的情况。

时间复杂度 \(\mathcal{O}(q\log n)\)，期望得分 \(100\)。

算法五

使用光速幂（分块预处理的快速幂），钦定 \(B=\sqrt{n}+1\)，处理出所有 \(0\leq i\leq B\) 的 \(m^i\) 与 \(m^{iB}\)，即可做到 \(\mathcal{O}(1)\) 查询 \(m\) 的幂。

时间复杂度 \(\mathcal{O}(q+\sqrt{n})\)，期望得分 \(100\)。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 1e6 + 5, mod = 998244353;
	struct node { LL v, l, r; LL val() { return v * (r - l + 1); } }; // val：求整段区间数的和
	LL n, m, q, qwq, cnt, ans, p1[N], p2[N]; pii a[N];
	vector<node> vec, now;
	LL qpow(LL k) { return p1[k % cnt] * p2[k / cnt] % mod; }
	LL add(LL& x, LL y) { return x = ((x + y) % mod + mod) % mod; }
	int main() {
		cin >> n >> m >> q, cnt = sqrt(n) + 1, p1[0] = p2[0] = 1;
		for (int i = 1; i <= cnt; i ++) p1[i] = p1[i - 1] * m % mod;
    	for (int i = 1; i <= cnt; i ++) p2[i] = p2[i - 1] * p1[cnt] % mod; // 光速幂
		for (int i = 1; i <= q; i ++) cin >> a[i].fi >> a[i].se;
		vec.push_back({1, 1, m}), qwq = 0; // 初值
		for (int i = 1; i <= q; ) {
			if (a[i].fi - qwq > 1) {
				LL sum = 0, k = a[i].fi - qwq;
				for (node v : vec) add(sum, v.val());
				vector<node>().swap(vec), vec.push_back({sum * qpow(k - 2) % mod, 1, m});
			} // 算法三
			qwq = a[i].fi, vector<node>().swap(now);
			LL l = 0, r = 0, pre = 1, sum = vec.front().val();
			while (a[i].fi == qwq) {
				if (pre < a[i].se) now.push_back({0, pre, a[i].se - 1});
				now.push_back({-1, a[i].se, a[i].se}), pre = a[i].se + 1, i ++;
			}
			if (pre <= m) now.push_back({0, pre, m});
			for (node &v : now) {
				if (v.v == -1) { v.v = 0; continue; }
				while (vec[l].r < v.l) add(sum, -vec[l ++].val());
				while (vec[r].r < v.r) add(sum, vec[++ r].val());
				v.v = ((sum - vec[l].v * (v.l - vec[l].l) - vec[r].v * (vec[r].r - v.r)) % mod + mod) % mod;
			} // 算法二
			vec.swap(now);
		}
		if (qwq < n) {
			LL sum = 0, k = n - qwq + 1;
			for (node v : vec) add(sum, v.val());
			vector<node>().swap(vec), vec.push_back({sum * qpow(k - 2) % mod, 1, m});
		} // 特判没有做完
		for (node v : vec) add(ans, v.val());
		cout << ans << '\n';
		return 0;
	}
}
int main() {
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}