結果

問題 No.840 ほむほむほむら
ユーザー krotonkroton
提出日時 2019-06-17 12:51:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 176 ms / 4,000 ms
コード長 4,779 bytes
コンパイル時間 1,342 ms
コンパイル使用メモリ 111,912 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-05 12:02:02
合計ジャッジ時間 3,063 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 24 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 8 ms
5,376 KB
testcase_08 AC 42 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 14 ms
5,376 KB
testcase_13 AC 112 ms
5,376 KB
testcase_14 AC 16 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 26 ms
5,376 KB
testcase_18 AC 141 ms
5,376 KB
testcase_19 AC 176 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 4 ms
5,376 KB
testcase_23 AC 164 ms
5,376 KB
testcase_24 AC 4 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 5 ms
5,376 KB
testcase_27 AC 161 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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 */

template <std::uint_fast64_t Modulus>
class modint {
  using u64 = std::uint_fast64_t;

 public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept
      : a(x % Modulus) {
  }
  constexpr u64 &value() noexcept {
    return a;
  }
  constexpr const u64 &value() const noexcept {
    return a;
  }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(const modint rhs) noexcept {
    return *this *= ~rhs;
  }
  constexpr modint operator^(u64 exp) const noexcept {
    modint v = 1, x = *this;
    while (exp) {
      if (exp & 1) {
        v *= x;
      }
      x *= x;
      exp >>= 1;
    }
    return v;
  }
  constexpr modint operator~() const noexcept {
    return *this ^ (Modulus - 2);
  }
};

using mint = modint<998244353>;

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(const Mat& A, const 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 solveNaive(int N, int K) {
  vec<mint, 3> dp = make_v(K, K, K, mint(0)); 
  dp[0][0][0] = 1;
  for (int t = 0; t < N; t++) {
    vec<mint, 3> ndp = make_v(K, K, K, mint(0)); 
    for (int a = 0; a < K; a++) {
      for (int b = 0; b < K; b++) {
        for (int c = 0; c < K; c++) {
          mint cur = dp[a][b][c];
          ndp[(a + 1) % K][b][c] += cur;
          ndp[a][(a + b) % K][c] += cur;
          ndp[a][b][(b + c) % K] += cur;
        }
      }
    }
    dp = ndp;
  }
  mint res = 0;
  for (int a = 0; a < K; a++) for (int b = 0; b < K; b++) res += dp[a][b][0];
  return res.value();
}

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.value();
}

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