M-SOLUTIONS Programming Contest 2021(AtCoder Beginner Contest 232)E - Rook Path

#include

using namespace std;

const int N = 1e6 +10;
const int mod = 998244353;

long long f[N][2][2];
int h, w, k;
int x1, x2, y1, y2;
int main () {
	cin >> h >> w >> k;
	cin >> x1 >> y1 >> x2 >> y2;
	
	int k1 = 0, k2 = 0;
	if (x1 == x2) k1 = 1;
	if (y1 == y2) k2 = 1;
	f[0][k1][k2] = 1;
	for (int i =1; i<= k; i ++) {
		f[i][1][0] = ((f[ i -1][1][0] * (w - 2) % mod + f[i - 1][0][0]) % mod + f[i - 1][1][1] * (w - 1) % mod) % mod;
		f[i][0][1] = ((f[i - 1][0][1] * (h - 2) % mod + f[i - 1][1][1] * (h - 1)) % mod+ f[i - 1][0][0]) %mod;
		f[i][0][0] = ((f[i - 1][0][0] * (h + w - 4) % mod + f[i - 1][1][0] * (h - 1)) % mod+ f[i - 1][0][1] * (w - 1) % mod) % mod;
		f[i][1][1] = (f[i - 1][1][0] + f[i - 1][0][1]) % mod;
	}
	cout << f[k][1][1] << endl;
	return 0;
}

每个题目都有简便的思考方式。我们要找到这种思考方式 当前i - 1步到下一步有多少种选择就乘多少