E - Rook Path

题意： 一个$n*m$的棋盘。初始点在 $(x1,y1)$ ， 求通过 $k$ 次移动后到达$(x2,y2)$的方案数。

注：每次移动可以 移至当前列/当前行的任意一点。（不能站着不动）

Solution：

首先可以得出简单dp方程：

$f_{i,j,k} = f_{i,j,k}=\sum_{j2}^{j2\ne j}f_{i,j2,k-1} + \sum_{i2}^{i2\ne i}f_{i2,j,k-1}$

简单手模之后我们可以发现一个显然的规律就是，对于一个$k$值，$f_{i,j}$只会有四个不同的取值，分别对应：

• $f_{0,0} =(x1, y1)$
• $f_{1,0} =(x, y1) \quad x\ne x1$
• $f_{0,1} =(x1, y) \quad y\ne y1$
• $f_{1,1} =(x,y) \quad x\ne x1 且y\ne y1$

dp方程也很好推且很好理解。算是一道优化状态的好题。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
/**/
const int mod = 998244353;
int n, m, t;
int x1, Y1, x2, y2;
int v00, v01, v10, v11;
int f[2][2];
/**/
signed main()
{
	cin >> n >> m >> t;
	cin >> x1 >> Y1 >> x2 >> y2;
	f[0][0] = 1;
	while(t--)
	{
		v00 = (f[1][0] * (n - 1) % mod + f[0][1] * (m - 1) % mod) % mod;
		v01 = (f[0][1] * (m - 2) % mod + f[1][1] * (n - 1) % mod + f[0][0]) % mod;
		v10 = (f[1][0] * (n - 2) % mod + f[1][1] * (m - 1) % mod + f[0][0]) % mod;
		v11 = (f[1][1] * (n + m - 4) % mod + f[0][1] + f[1][0]) % mod;
		f[0][0] = v00, f[0][1] = v01, f[1][0] = v10, f[1][1] = v11;
	}
	cin >> x1 >> Y1 >> x2 >> y2;
	if(x1 == x2 && Y1 == y2) cout << f[0][0];
	else if(x1 == x2 && Y1 != y2) cout << f[0][1];
	else if(x1 != x2 && Y1 == y2) cout << f[1][0];
	else cout << f[1][1];
	return 0;
}