結果
問題 | No.840 ほむほむほむら |
ユーザー | pekempey |
提出日時 | 2019-06-14 21:56:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 314 ms / 4,000 ms |
コード長 | 2,696 bytes |
コンパイル時間 | 1,783 ms |
コンパイル使用メモリ | 170,156 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-08-08 23:38:16 |
合計ジャッジ時間 | 4,542 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 7 ms
4,376 KB |
testcase_03 | AC | 44 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 15 ms
4,380 KB |
testcase_08 | AC | 79 ms
4,376 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 3 ms
4,380 KB |
testcase_12 | AC | 23 ms
4,380 KB |
testcase_13 | AC | 204 ms
4,380 KB |
testcase_14 | AC | 27 ms
4,376 KB |
testcase_15 | AC | 2 ms
4,380 KB |
testcase_16 | AC | 4 ms
4,380 KB |
testcase_17 | AC | 48 ms
4,380 KB |
testcase_18 | AC | 258 ms
4,380 KB |
testcase_19 | AC | 314 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 6 ms
4,376 KB |
testcase_23 | AC | 300 ms
4,384 KB |
testcase_24 | AC | 5 ms
4,380 KB |
testcase_25 | AC | 1 ms
4,380 KB |
testcase_26 | AC | 7 ms
4,380 KB |
testcase_27 | AC | 301 ms
4,380 KB |
ソースコード
#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'; }