結果

問題 No.1241 Eternal Tours
コンテスト
ユーザー hitonanode
提出日時 2020-08-25 22:37:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,879 bytes
コンパイル時間 845 ms
コンパイル使用メモリ 78,860 KB
最終ジャッジ日時 2025-01-13 14:51:50
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1 TLE * 1
other AC * 17 RE * 18 TLE * 3 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <array>
#include <iostream>
#include <set>
#include <vector>

// ナイーブな行列累乗解 (盤面が広すぎるのでTLE)
// Complexity: O((HW)^3 logT), H = (2^^X) - 1, W = (2^^Y) - 1

template <int mod>
struct ModInt
{
    using lint = long long;
    int val;
    constexpr ModInt() : val(0) {}
    constexpr ModInt &_setval(lint v) { val = (v >= mod ? v - mod : v); return *this; }
    constexpr ModInt(lint v) { _setval(v % mod + mod); }
    explicit operator bool() const { return val != 0; }
    constexpr ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val + x.val); }
    constexpr ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val - x.val + mod); }
    constexpr ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val * x.val % mod); }
    constexpr ModInt operator-() const { return ModInt()._setval(mod - val); }
    constexpr ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    constexpr ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    constexpr ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
    friend constexpr ModInt operator+(lint a, const ModInt &x) { return ModInt()._setval(a % mod + x.val); }
    friend constexpr ModInt operator-(lint a, const ModInt &x) { return ModInt()._setval(a % mod - x.val + mod); }
    friend constexpr ModInt operator*(lint a, const ModInt &x) { return ModInt()._setval(a % mod * x.val % mod); }
};
template <typename T>
struct matrix
{
    int H, W;
    std::vector<T> elem;
    typename std::vector<T>::iterator operator[](int i) { return elem.begin() + i * W; }
    inline T &at(int i, int j) { return elem[i * W + j]; }
    inline T get(int i, int j) const { return elem[i * W + j]; }
    operator std::vector<std::vector<T>>() const {
        std::vector<std::vector<T>> ret(H);
        for (int i = 0; i < H; i++) std::copy(elem.begin() + i * W, elem.begin() + (i + 1) * W, std::back_inserter(ret[i]));
        return ret;
    }

    matrix() = default;
    matrix(int H, int W) : H(H), W(W), elem(H * W) {}
    matrix operator*(const matrix &r) const {
        matrix ret(H, r.W);
        for (int i = 0; i < H; i++) {
            for (int k = 0; k < W; k++) {
                for (int j = 0; j < r.W; j++) {
                    ret.at(i, j) += this->get(i, k) * r.get(k, j);
                }
            }
        }
        return ret;
    }
    matrix &operator*=(const matrix &r) { return *this = *this * r; }
    friend std::vector<T> operator*(const matrix &m, const std::vector<T> &v) {
        assert(m.W == int(v.size()));
        std::vector<T> ret(m.H);
        for (int i = 0; i < m.H; i++) {
            for (int j = 0; j < m.W; j++) {
                ret[i] += m.get(i, j) * v[j];
            }
        }
        return ret;
    }
};


using mint = ModInt<998244353>;
using namespace std;

array<int, 4> dx{1, -1, 0, 0};
array<int, 4> dy{0, 0, 1, -1};
int main()
{
    int X, Y;
    long long T;
    int a, b, c, d;
    cin >> X >> Y >> T >> a >> b >> c >> d;

    int H = (1 << X) - 1, W = (1 << Y) - 1;


    auto hw2id = [&](int h, int w) -> int {
        if (h < 0 or h >= H or w < 0 or w >= W) return -1;
        else return h * W + w;
    };

    matrix<mint> trans(H * W, H * W);
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            int from = hw2id(i, j);
            trans[from][from] = 1;
            for (int d = 0; d < 4; d++)
            {
                int to = hw2id(i + dx[d], j + dy[d]);
                if (to != -1) trans[to][from] = 1;
            }
        }
    }
    vector<mint> dp(H * W);
    dp[hw2id(a - 1, b - 1)] = 1;
    while (T)
    {
        if (T & 1) dp = trans * dp;
        trans *= trans;
        T >>= 1;
    }
    cout << dp[hw2id(c - 1, d - 1)].val << '\n';
}
0