Submission #66653512

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)

int main(){
    int H, W;
    cin >> H >> W;
    if (H < W) swap(H, W);
    vector<mint> dpC(W + 1), dpS(W + 1);
    vector<mint> fact(W + 2, 1), invfact(W + 2, 1);
    rep(i, 0, W + 1) fact[i + 1] = fact[i] * (i + 1);
    invfact[W + 1] = fact[W + 1].inv();
    for (int i = W + 1; i > 0; i--) invfact[i - 1] = invfact[i] * i;
    dpC[0] = 1;
    rep(rp, 0, H){
        vector<mint> n_dpC(W + 1), n_dpS(W + 1);
        rep(i, 0, W + 1){
            rep(j, i, W + 1){
                n_dpC[j] += dpC[i] * invfact[j - i + 1] * (j + 1);
                n_dpS[j] += dpS[i] * invfact[j - i + 1] * (j + 1);
                n_dpS[j] += dpC[i] * i * invfact[j - i + 2] * (j + 1);
            }
        }
        swap(n_dpS, dpS);
        swap(n_dpC, dpC);
        rep(i, 0, W + 1) dpS[i] += dpC[i] * (W - i);
    }
    mint ans = 0;
    rep(i, 0, W + 1) ans += dpS[i] * invfact[W - i];
    rep(i, 1, W + 1) ans *= i;
    cout << ans.val() << "\n";
}

Submission Info

Judge Result