結果

問題 No.840 ほむほむほむら
コンテスト
ユーザー kcvlex
提出日時 2019-06-15 00:32:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 506 ms / 4,000 ms
コード長 3,437 bytes
コンパイル時間 1,733 ms
コンパイル使用メモリ 174,556 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2024-11-15 17:54:04
合計ジャッジ時間 5,368 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
#include "../debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

const ll mod = 998244353;

using Mat = VV<ll>;

Mat make_mat(ll r, ll c) { return move(make_v<ll>(0, r, c)); }
Mat make_id(ll r, ll c) {
    auto ret = make_v<ll>(0, r, c);
    for(ll i = 0; i < min(r, c); i++) ret[i][i] = 1;
    return move(ret);
}
Mat make_id(const Mat &a) { return move(make_id(a.size(), a[0].size())); }

Mat operator*(const Mat &a, const Mat &b) {
    Mat ret = make_mat(a.size(), b[0].size());
    for(ll i = 0; i < ret.size(); i++) {
        for(ll j = 0; j < ret[0].size(); j++) {
            ll tmp = 0;
            for(ll k = 0; k < a[0].size(); k++) (tmp += a[i][k] % mod * b[k][j] % mod) %= mod;
            ret[i][j] = tmp;
        }
    }
    return move(ret);
}

Mat pow__(Mat a, ll b) { return b ? (b & 1 ? a : make_id(a)) * pow__(a * a, b / 2) : make_id(a); }
ll pow__(ll a, ll b) { return b ? (b & 1 ? a : 1) * pow__(a * a % mod, b / 2) % mod : 1; }

int main() {
    ll N, K;
    cin >> N >> K;
    Mat mat = make_mat(K * K * K, K * K * K);
    Mat init = make_mat(K * K * K, 1);
    init[0][0] = 1;

    auto make_idx = [&](ll a, ll b, ll c) {
        ll ret = 0;
        ll tmp[] = { a, b, c, };
        for(ll i = 0; i < 3; i++) {
            ret = ret * K + tmp[i] % K;
        }
        return ret;
    };

    for(ll i = 0; i < mat.size(); i++) {
        ll homura = i % K;
        ll homu = i / K % K;
        ll ho = i / K / K % K;
        mat[i][make_idx(ho, homu, homura + homu)]++;
        mat[i][make_idx(ho, homu + ho, homura)]++;
        mat[i][make_idx(ho + 1, homu, homura)]++;
    }
    
    mat = pow__(mat, N);
    init = mat * init;
    ll ans = 0;
    for(ll i = 0; i < init.size(); i++) {
        if(i % K) continue;
        (ans += init[i][0]) %= mod;
    }
    cout << ans << endl;
    return 0;
}
0