提出 #28081036

---

ソースコード 拡げる

#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 ll MOD = 998244353;
using Matrix = vector<vector<ll>>;

Matrix transitionMatrix(ll H, ll W) {
    return {
        {H+W-4, W-1, H-1, 0},
        {1, H-2, 0, H-1},
        {1, 0, W-2, W-1},
        {0, 1, 1, 0},
    };
}

Matrix mulMat(Matrix A, Matrix B) {
    Matrix C(4, vector<ll>(4));

    rep(i,4) {
        rep(j,4) {
            rep(k,4) {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= MOD;
            }
        }
    }

    return C;
}

Matrix expMatMod(Matrix A, ll K) {
    Matrix ans = Matrix(4, vector<ll>(4, 0));
    Matrix mat = Matrix(4, vector<ll>(4, 0));
    rep(i,4) ans[i][i] = 1;
    rep(i,4) mat[i][i] = 1;

    for (ll i = 0;; i++) {
        if (i == 0) mat = A;
        else mat = mulMat(mat, mat);

        if (K&1) ans = mulMat(ans, mat);
        K/=2;
        if (K == 0) break;
    }

    return ans;
}

void solve() {
    ll H, W, K;
    cin >> H >> W >> K;
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    Matrix trans = transitionMatrix(H, W);
    vector<ll> state(4, 0);

    int stateidx = ((x1==x2) << 1) + (y1==y2);
    state[stateidx] = 1;

    Matrix A = expMatMod(trans, K);
    // vector<ll> ans(4, 0);
    // rep(i,4) {
    //     rep(j,4) {
    //         ans[i] += A[i][j] * state[j];
    //     }
    // }
    // 
    // cout << ans[3] << endl;

    cout << A[3][stateidx] << endl;
}

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

提出情報

ジャッジ結果