AtCoder Beginner Contest 232 E

Problem Statement

The difficulty of this question is around 1400.
https://atcoder.jp/contests/abc232/tasks/abc232_e

We could solve this question by dynamic programming. Here I take bottom-up approach.

State Definition

We define the state as follows:

dp[ i ][ j ] = The number of ways to do the i operations and land on the points that:
with different row and column of destination, when j = 0;
with same row and different column of destination, when j = 1;
with different row and same column of destination, when j = 2;
with same row and col of destination, when j = 3;

State Transition

In implementation, we should take modulo 998244353.

transition.cpp

dp[0][i] = (H - 2 + W - 2) * dp[0][i - 1] + (W - 1) * dp[2][i - 1] + (H - 1) * dp[1][i - 1];

dp[1][i] = dp[0][i - 1] + (W - 2) * dp[1][i - 1] + (W - 1) * dp[3][i - 1];

dp[2][i] = dp[0][i - 1] + (H - 2) * dp[2][i - 1] + (H - 1) * dp[3][i - 1];

dp[3][i] = dp[1][i - 1] + dp[2][i - 1];

My answer

I solved it after contest time.

E.cpp

# include <bits/stdc++.h>
using namespace std;
using ll = long long;
# define rep0(i, n) for (int i = 0; i < (int)(n); ++i)

ll MOD = 998244353;
ll dp[5][1000005];

int main() {
    ll H, W, K, x1, y1, x2, y2;
    cin >> H >> W >> K;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x1 != x2 && y1 != y2) dp[0][0] = 1; // different rows & columns
    if (x1 == x2 && y1 != y2) dp[1][0] = 1; // same row
    if (x1 != x2 && y1 == y2) dp[2][0] = 1; // same column
    if (x1 == x2 && y1 == y2) dp[3][0] = 1; // same point as destination
    
    for (int i = 1; i <= K; ++i) {
        // different rows & columns
        dp[0][i] = ((H - 2 + W - 2) * dp[0][i - 1] % MOD + (W - 1) * dp[2][i - 1] % MOD + (H - 1) * dp[1][i - 1] % MOD) % MOD;
        // same row
        dp[1][i] = (dp[0][i - 1] % MOD + (W - 2) * dp[1][i - 1] % MOD + (W - 1) * dp[3][i - 1] % MOD) % MOD;
        // same column
        dp[2][i] = (dp[0][i - 1] % MOD + (H - 2) * dp[2][i - 1] % MOD + (H - 1) * dp[3][i - 1] % MOD) % MOD;
        // same point as destination
        dp[3][i] = (dp[1][i - 1] + dp[2][i - 1]) % MOD;
    }
    cout << dp[3][K] % MOD << endl;
}