結果

問題 No.840 ほむほむほむら
コンテスト
ユーザー pekempey
提出日時 2019-06-14 21:56:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 406 ms / 4,000 ms
コード長 2,696 bytes
コンパイル時間 1,822 ms
コンパイル使用メモリ 172,824 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-14 04:33:57
合計ジャッジ時間 4,937 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
using namespace std;
using ll = long long;

const int MOD = 998244353;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator-(mint a) {
  return -a.n + MOD * (a.n != 0);
}
mint operator+(mint a, mint b) {
  int x = a.n + b.n;
  return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
  int x = a.n - b.n;
  return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) {
  return (long long)a.n * b.n % MOD;
}
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }



template<class T>
struct matrix {
  int n;
  vector<T> dat;

  matrix(int n_) : n(n_), dat(n_ * n_) {}

  matrix(initializer_list<initializer_list<T>> a) {
    n = a.size();
    dat.reserve(n * n);
    for (initializer_list<T> x : a) {
      assert(x.size() == n);
      for (T y : x) {
        dat.push_back(y);
      }
    }
  }

  T &operator()(int i, int j) {
    assert(0 <= i && i < n && 0 <= j && j < n);
    return dat[i * n + j];
  }
};

template<class T>
matrix<T> operator*(matrix<T> a, matrix<T> b) {
  const int n = a.n;
  matrix<T> c(n);
  for (int i = 0; i < n; i++) {
    for (int k = 0; k < n; k++) {
      for (int j = 0; j < n; j++) {
        c(i, j) += a(i, k) * b(k, j);
      }
    }
  }
  return c;
}

template<class T>
matrix<T> &operator*=(matrix<T> &a, matrix<T> b) {
  return a = a * b;
}

template<class T>
matrix<T> pow(matrix<T> a, long long b) {
  matrix<T> res(a.n);
  for (int i = 0; i < a.n; i++) {
    res(i, i) = 1;
  }
  for (; b > 0; a *= a, b >>= 1) {
    if (b & 1) res *= a;
  }
  return res;
}

template<class T>
ostream &operator<<(ostream &o, matrix<T> a) {
  o << '[';
  for (int i = 0; i < a.n; i++) {
    if (i > 0) o << ' ';
    o << '[';
    for (int j = 0; j < a.n; j++) {
      if (j > 0) o << ' ';
      o << a(i, j);
    }
    o << ']';
  }
  o << ']';
  return o;
}


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, K;
  cin >> N >> K;
  matrix<mint> A(K*K*K);
  auto f = [&](int i, int j, int k) {
    i %= K;
    j %= K;
    k %= K;
    return i * K * K + j * K + k;
  };
  rep(i, K) rep(j, K) rep(k, K) {
    int x = f(i, j, k);
    // ho
    A(f(i+1,j,k), x) += 1;
    // mu
    A(f(i,j+i,k), x) += 1;
    // ra
    A(f(i,j,k+j), x) += 1;
  }
  A = pow(A, N);
  mint ans;
  rep(i, K) rep(j, K) {
    ans += A(0, f(i, j, 0));
  }
  cout << ans << '\n';
}
0