結果
問題 | 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 |
ソースコード
#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'; }