[ABC232E] Rook Path
cloud2764scallop_eve
·
·
题解
题意
在象棋棋盘上有一个车，它的位置是 (x1,y1)，求车从此处到达 (x2,y2) 有多少种情况。
思路
明显的组合数学与 DP 题。
最最最先，一定要明确一个概念，车可以横向或竖向移动到当前列或行的任意一个（除去它本身现在的位置），但不可以斜着移动。
如图所示，(x1,y1) 是车当前的位置，标注 1 的位置是车可以一步到达的，而标注 0 的位置则意味着不可以一步到达。
考虑暴力 DP。设 dp_{x, y, k} 表示进行了 k 次操作后车走到 (x, y) 的方案数。
状态转移方程为：
dp_{x, y, k} = \sum_{1 \le i \le H,i \neq x} dp_{i, y, k - 1} + \sum_{1 \le i \le W,i \neq y} dp_{x, j, k - 1}
最终答案为 dp_{x2, y2, k}。
但这样高达 O(kH^3) 的优秀时间复杂度，再水的数据都明显过不了。
考虑优化。
我们可以设四个集合，分别表示：
可以表示为：
$S_{0, 1} = {(x, y) \mid x = x1, y \neq y1}$；
$S_{1, 0} = {(x, y) \mid x \neq x1, y = y1}$；
$S_{1, 1} = {(x, y) \mid x \neq x1, y \ neq y1}$。
观察四个集合，可以看出当 $a, b \in {0, 1}$ 且 $(x1, y1)(x2, y2) \in S_{a, b}$ 时，$dp_{x1, y1, k} = dp_{x2, y2, k}(0 \le k \le K)$。
当 $k$ 相同时，同一个集合内的所有点的 $dp$ 值是相同的。
所以不妨设：
$$f_{n, m, k}(n, m \in {0, 1}) = \sum_{(x, y) \in S_{a, b}} dp_{x, y, k}$$
那么 $f$ 的边界条件也就很好处理了。分别是：
1. $f_{0, 0, 0} = 1$；
2. $f_{0, 1, 0} = 0$；
3. $f_{1, 0, 0} = 0$；
4. $f_{1, 1, 0} = 0$。
现在就可以推导转移方程了。方便起见，可以先分情况讨论：
- $x1 = x2$ 且 $y1 = y2$：$ans = f_{0, 0, k}$；
- $x1 = x2$ 且 $y1 \neq y2$：$ans = \frac{f_{0, 1, K}}{W - 1}$；
- $x1 \neq x2$ 且 $y1 = y2$：$ans = \frac{f_{0, 1, K}}{H - 1}$；
- $x1 \neq x2$ 且 $y1 \neq y2$：$ans = \frac{f_{0, 1, K}}{(W - 1) \times (H - 1)}$。
那么转移方程就应为：
- $f_{0, 0, k} = f_{0, 1, k - 1} + f_{1, 0, k - 1}$；
- $f_{0, 1, k} = (W - 1) \times f_{0, 0, k - 1} + (W - 2) \times f_{0, 1, k - 1} + f_{1, 1, k - 1}$；
- $f_{1, 0, k} = (H - 1) \times f_{0, 0, k - 1} + (H - 2) \times f_{1, 0, k - 1} + f_{1, 1, k - 1}$；
- $f_{1, 1, k} = (W - 1) \times f_{0, 1, k - 1} + (H - 1) \times f_{1, 0, k - 1} + (W + H - 4) \times f_{1, 1, k - 1}$。
得解。
## 代码
除法需要使用乘法逆元。
**所用的函数请务必使用 `long long`！**
不然就会：[R.I.P](https://atcoder.jp/contests/abc232/submissions/48990002)。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353, N = 1e7 + 5;
int n, m, k, x, y, xx, yy;
int ans;
int f[2][2][N];
int inv(int x) {
return x == 1 ? 1 : (mod - mod / x) * inv(mod % x) % mod;
}
signed main() {
scanf("%lld%lld%lld", &n, &m, &k);
scanf("%lld%lld%lld%lld", &x, &y, &xx, &yy);
f[0][0][0] = 1;
for (int i = 1; i <= k; i++) {
f[0][0][i] = (f[0][1][i - 1] + f[1][0][i - 1]) % mod;
f[0][1][i] = ((m - 1) * f[0][0][i - 1] % mod + (m - 2) * f[0][1][i - 1] % mod + f[1][1][i - 1] % mod + mod) % mod;
f[1][0][i] = ((n - 1) * f[0][0][i - 1] % mod + (n - 2) * f[1][0][i - 1] % mod + f[1][1][i - 1] % mod + mod) % mod;
f[1][1][i] = ((n - 1) * f[0][1][i - 1] % mod + (m - 1) * f[1][0][i - 1] % mod + (n + m - 4) * f[1][1][i - 1] % mod + mod) % mod;
}
if (x == xx && y == yy) ans = f[0][0][k];
else if (x == xx && y != yy) ans = f[0][1][k] * inv(m - 1) % mod;
else if (x != xx && y == yy) ans = f[1][0][k] * inv(n - 1) % mod;
else ans = f[1][1][k] * inv((n - 1) * (m - 1) % mod) % mod;
printf("%lld\n", ans);
return 0;
}
```