#1173139 (C++23) No.3600 Moving Queen Many Times

• 問題: No.3600 Moving Queen Many Times
• ユーザー: abc864197532
• 提出日時: 2026-07-24 22:12:33
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 359 ms / 7,000 ms
• コード長: 3,112 bytes
• コンパイル時間: 2,494 ms
• コンパイル使用メモリ: 349,156 KB
• 実行使用メモリ: 112,512 KB
• 最終ジャッジ日時: 2026-07-24 22:15:44
• 合計ジャッジ時間: 7,891 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 75

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
#ifdef Doludu
template <typename T>
ostream& operator << (ostream &o, vector <T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif
const int mod = 998244353, N = 300005;

int add(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
int mul(int a, int b) { return 1ll * a * b % mod; }
int Pow(int a, int b) { int ans = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a); return ans; }

auto matmul(auto a, auto b) {
    vector c(sz(a), vector(sz(a), 0));
    for (int i = 0; i < sz(a); ++i) {
        for (int j = 0; j < sz(a); ++j) {
            for (int k = 0; k < sz(a); ++k) {
                c[i][k] = add(c[i][k], mul(a[i][j], b[j][k]));
            }
        }
    }
    return c;
}

void solve() {
    int n, m, x1, y1, x2, y2;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2, --x1, --y1, --x2, --y2;
    auto good = [&](int i, int j) {
        int x1_ = i / m, y1_ = i % m, x2_ = j / m, y2_ = j % m;
        if (i == j) return false;
        return x1_ == x2_ || y1_ == y2_ || x1_ + y1_ == x2_ + y2_ || x1_ - y1_ == x2_ - y2_;
    };
    vector dp(1 << (n * m), vector(n * m, vector(n * m, 0)));
    for (int i = 0; i < n * m; ++i) dp[0][i][i] = 1;
    for (int msk = 0; msk < 1 << (n * m); ++msk) {
        for (int i = 0; i < n * m; ++i) {
            for (int j = 0; j < n * m; ++j) if (dp[msk][i][j]) {
                for (int k = 0; k < n * m; ++k) if (~msk >> k & 1 && good(j, k)) {
                    dp[msk ^ (1 << k)][i][k] = add(dp[msk ^ (1 << k)][i][k], dp[msk][i][j]);
                }
            }
        }
    }
    vector mat(n * m, vector(n * m, 0));
    for (int i = 0; i < n * m; ++i) {
        for (int j = 0; j < n * m; ++j) {
            mat[i][j] = dp.back()[i][j];
        }
    }

    ll k; cin >> k;
    ll round = k / (n * m);
    vector res(n * m, vector(n * m, 0));
    for (int i = 0; i < n * m; ++i) res[i][i] = 1;
    for (; round; round >>= 1, mat = matmul(mat, mat)) {
        if (round & 1) res = matmul(res, mat);
    }

    int s = x1 * m + y1, t = x2 * m + y2;
    int ans = 0;
    int cnt = k % (n * m);
    for (int msk = 0; msk < 1 << n * m; ++msk) if (__builtin_popcount(msk) == cnt) {
        for (int x = 0; x < n * m; ++x) {
            ans = add(ans, mul(res[s][x], dp[msk][x][t]));
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}