結果

問題 No.3600 Moving Queen Many Times
コンテスト
ユーザー 👑 AngrySadEight
提出日時 2026-06-13 00:27:09
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,318 ms / 7,000 ms
+ 188µs
コード長 2,934 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,582 ms
コンパイル使用メモリ 182,116 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2026-07-24 20:30:24
合計ジャッジ時間 15,385 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 75
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

vector<vector<mint>> m_mul(vector<vector<mint>> &a, vector<vector<mint>> &b) {
    ll n = a.size();
    vector<vector<mint>> ret(n, vector<mint>(n, mint(0)));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            for (ll k = 0; k < n; k++) {
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]);
            }
        }
    }
    return ret;
}

vector<vector<mint>> p_mul(vector<vector<mint>> a, ll k) {
    ll n = a.size();
    vector<vector<mint>> ret(n, vector<mint>(n, mint(0)));
    for (ll i = 0; i < n; i++) {
        ret[i][i] = mint(1);
    }
    while (k > 0) {
        if (k % 2 == 1) {
            ret = m_mul(a, ret);
        }
        a = m_mul(a, a);
        k /= 2;
    }
    return ret;
}

int main(){
    ll H, W, sx, sy, gx, gy, K;
    cin >> H >> W >> sx >> sy >> gx >> gy >> K;
    sx--;
    sy--;
    gx--;
    gy--;

    vector<vector<ll>> mat(H * W, vector<ll>(H * W, 0));
    for (ll i = 0; i < H; i++){
        for (ll j = 0; j < W; j++){
            for (ll k = 0; k < H; k++){
                for (ll l = 0; l < W; l++){
                    if (i == k && j == l) continue;
                    if (i == k || j == l || i + j == k + l || i - j == k - l){
                        mat[i * W + j][k * W + l] = 1;
                    }
                }
            }
        }
    }
    vector<vector<mint>> cnts_all(H * W, vector<mint>(H * W, mint(0)));
    vector<vector<vector<mint>>> cnts_part(H * W, vector<vector<mint>>(H * W, vector<mint>(H * W + 1, mint(0))));
    for (ll i = 0; i < H * W; i++){ 
        vector<vector<mint>> bitdp(1 << (H * W), vector<mint>(H * W, mint(0)));
        bitdp[0][i] = mint(1);
        for (ll j = 0; j < (1 << (H * W)); j++){
            for (ll k = 0; k < H * W; k++){
                for (ll l = 0; l < H * W; l++){
                    if ((j >> l) & 1) continue;
                    if (mat[k][l] == 0) continue;
                    bitdp[j + (1 << l)][l] += bitdp[j][k];
                }
            }
        }
        for (ll j = 0; j < H * W; j++){
            cnts_all[i][j] = bitdp[(1 << (H * W)) - 1][j];
        }
        for (ll j = 0; j < (1 << (H * W)); j++){
            ll popcnt = 0;
            for (ll k = 0; k < H * W; k++){
                if ((j >> k) & 1) popcnt++;
            }
            for (ll k = 0; k < H * W; k++){
                cnts_part[i][k][popcnt] += bitdp[j][k];
            }
        }
    }

    ll div = K / (H * W);
    ll rem = K % (H * W);

    vector<vector<mint>> mat_pow = p_mul(cnts_all, div);

    mint ans = mint(0);
    // (div * (H * W)) 回後の経由地を全探索する
    for (ll i = 0; i < H * W; i++){
        ans += mat_pow[sx * W + sy][i] * cnts_part[i][gx * W + gy][rem];
    }
    cout << ans.val() << endl;
}
0