結果

問題 No.840 ほむほむほむら
コンテスト
ユーザー バイト
提出日時 2019-06-19 23:51:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,315 bytes
コンパイル時間 1,097 ms
コンパイル使用メモリ 103,452 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 14:12:24
合計ジャッジ時間 4,294 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 8 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template<class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template<class T> struct _vec<T, 0> { using type = T; };
template<class T, size_t D> using vec = typename _vec<T, D>::type;
template<class T> vector<T> make_v(size_t size, const T &init) { return vector<T>(size, init); }
template<class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template<class T> inline void chmin(T &a, const T &b) { if (b < a) a = b; }
template<class T> inline void chmax(T &a, const T &b) { if (b > a) a = b; }
/* clang-format on */

//@formatter:off
//constexpr
int MOD = 998244353;

struct mint {    int x;    mint() : x(0) {}    mint(int a) {        x = a % MOD;        if (x < 0) x += MOD;    }    mint &operator+=(mint that) {        x = (x + that.x) % MOD;        return *this;    }    mint &operator-=(mint that) {        x = (x + MOD - that.x) % MOD;        return *this;    }    mint &operator*=(mint that) {        x = (int) x * that.x % MOD;        return *this;    }    mint &operator/=(mint that) { return *this *= that.inverse(); }    mint operator-() { return mint(-this->x); }    friend ostream &operator<<(ostream &out, mint m) { return out << m.x; }    mint inverse() {        int a = x, b = MOD, u = 1, v = 0;        while (b) {            int t = a / b;            a -= t * b;            u -= t * v;            swap(a, b);            swap(u, v);        }        return mint(u);    }mint operator+(mint that) { return mint(*this) += that; }    mint operator-(mint that) { return mint(*this) -= that; }    mint operator*(mint that) { return mint(*this) *= that; }    mint operator/(mint that) { return mint(*this) /= that; }    bool operator ==(mint that) const { return x == that.x; }    bool operator !=(mint that) const { return x != that.x; }    bool operator <(mint that) const { return x < that.x; }    bool operator <=(mint that) const { return x <= that.x; }    bool operator >(mint that) const { return x > that.x; }    bool operator >=(mint that) const { return x >= that.x; }};
istream &operator>>(istream &i, mint &a) {    i >> a.x;    return i;}
typedef vector<mint> vm;
vector<mint> fac, finv;
int mint_len = 1400000;              //既に変更されていたら変えない
mint com(int a, int b) {    if (a < 0) return 0;    if (b < 0 || b > a) return 0;    return fac[a] * finv[a - b] * finv[b];}
mint hom(int a, int b) {    return com(a + b - 1, b);}
template<typename T, typename U>  mint mpow(const T a, const U b) {    assert(b >= 0);    int x = a, res = 1;    U p = b;    while (p > 0) {        if (p & 1) (res *= x) %= MOD;        (x *= x) %= MOD;        p >>= 1;    }    return res;}
template<typename T> inline mint mpow(const T a, const mint b) {    int x = a, res = 1;    int p = b.x;    while (p > 0) {        if (p & 1) (res *= x) %= MOD;        (x *= x) %= MOD;        p >>= 1;    }    return res;}
using PM = pair<mint, mint>;
using vm = vector<mint>;
#define vvm(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(mint,__VA_ARGS__)

#define smod setmod
//setmodを呼ぶ @formatter:on


typedef vector<mint> Vec;
typedef vector<Vec> Mat;

Mat eye(int n) {
    Mat I(n, Vec(n));
    for (int i = 0; i < n; ++i)
        I[i][i] = 1;
    return I;
}
Mat mul(Mat A, const Mat &B) {
    for (int i = 0; i < A.size(); ++i) {
        Vec x(A[0].size());
        for (int k = 0; k < B.size(); ++k)
            for (int j = 0; j < B[0].size(); ++j)
                x[j] += A[i][k] * B[k][j];
        A[i].swap(x);
    }
    return A;
}
Mat pow(Mat A, ll k) {
    Mat X = eye(A.size());
    for (; k > 0; k /= 2) {
        if (k & 1) X = mul(X, A);
        A = mul(A, A);
    }
    return X;
}
Vec mul(Mat &A, Vec &b) {
    Vec y(A.size());
    for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < A[0].size(); ++j)
            y[i] += A[i][j] * b[j];
    return y;
}

ll solve(int N, int K) {
    int dim = K * K * K;
    auto encode = [&](int a, int b, int c) {
        return a * K * K + b * K + c;
    };
    Mat A = make_v(dim, dim, mint(0));
    for (int a = 0; a < K; a++) {
        for (int b = 0; b < K; b++) {
            for (int c = 0; c < K; c++) {
                int cur = encode(a, b, c);
                A[encode((a + 1) % K, b, c)][cur] += 1;
                A[encode(a, (a + b) % K, c)][cur] += 1;
                A[encode(a, b, (b + c) % K)][cur] += 1;
            }
        }
    }
    A = pow(A, N);
    Vec init(dim);
    init[0] = 1;
    auto goal = mul(A, init);
    mint res = 0;
    for (int a = 0; a < K; a++) {
        for (int b = 0; b < K; b++) {
            res += goal[encode(a, b, 0)];
        }
    }
    return res.x;
}

int main() {
#ifdef DEBUG
    ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
    int N, K;
    while (cin >> N >> K) {
        cout << solve(N, K) << endl;
    }
    return 0;
}
0