Submission #28025623

---

Source Code Expand

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,k,n) for (int i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
// using P = pair<ll,ll>;

const ll INF = (ll)1e18;
// const int INF = (int)1e9+7;
template<typename T>
void chmin(T &a, T b) { a = min(a, b); }
template<typename T>
void chmax(T &a, T b) { a = max(a, b); }

// const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

void solve() {
    mint H, W;
    int K;
    cin >> H >> W >> K;

    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    vector<vector<mint>> dp(2, vector<mint>(2, 0));
    dp[x1==x2][y1==y2] = 1;

    while (K--) {
        vector<vector<mint>> nx(2, vector<mint>(2,0));
        nx[0][0] = (W-1)*dp[0][1] + (H-1)*dp[1][0] + (H+W-4)*dp[0][0];
        nx[0][1] = dp[0][0] + (H-2)*dp[0][1] + (H-1)*dp[1][1];
        nx[1][0] = dp[0][0] + (W-2)*dp[1][0] + (W-1)*dp[1][1];
        nx[1][1] = dp[0][1] + dp[1][0];
        swap(dp, nx);
    }

    cout << dp[1][1] << endl;
}

int main() {
    solve();
    return 0;
}

Submission Info

Judge Result