結果

問題 No.840 ほむほむほむら
コンテスト
ユーザー yantaro
提出日時 2026-04-01 09:48:56
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 480 ms / 4,000 ms
コード長 2,733 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,756 ms
コンパイル使用メモリ 219,568 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-04-01 09:49:01
合計ジャッジ時間 5,588 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//python3 expander.py main.cpp

using ll = long long;
using ld = long double;
using lll = __int128_t;

//using mint = modint; //mint::set_mod(M);
//using mint = modint998244353;
//using mint = modint1000000007;

template<class T> using pq = priority_queue<T>; //大きい順
template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>; //小さい順

#define vec_unique(v) v.erase(unique(v.begin(), v.end()), v.end()) //重複削除
#define vec_iota(v) iota(v.begin(), v.end(), 0) //0, 1, 2, 3, ..., n - 1にセット
#define concat(a, b) a.insert(a.end(), b.begin(), b.end())
#define debug(x) cerr << #x << " = " << x << endl
#define maxvalue(array) *max_element(array.begin(), array.end())
#define minvalue(array) *min_element(array.begin(), array.end())
#define sumvalue(array) accumulate(array.begin(), array.end(), 0ll)
#define popcount(x) __builtin_popcountll(x)

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
//int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

#define INF 2e18
#define INF2 2e9

//行列乗算
vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
    int n = a.size();
    vector<vector<ll>> res(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		    for (int k = 0; k < n; k++) {
				res[i][j] += a[i][k] * b[k][j];
				res[i][j] %= mod;
			}
		}
	}
	return res;
}

//行列累乗
vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
    int n = a.size();
    vector<vector<ll>> res(n, vector<ll>(n));
    for(int i = 0; i < n; i++) res[i][i] = 1;
    while(b) {
        if(b & 1) res = mat_mul(res, a, mod);
        a = mat_mul(a, a, mod);
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    int k;
    cin >> n >> k;
    vector<vector<ll>> m(k * k * k, vector<ll>(k * k * k));
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k; j++) {
            for(int l = 0; l < k; l++) {
                m[((i + 1) % k) * k * k + j * k + l][i * k * k + j * k + l]++;
                m[i * k * k + ((j + i) % k) * k + l][i * k * k + j * k + l]++;
                m[i * k * k + j * k + ((l + j) % k)][i * k * k + j * k + l]++;
            }
        }
    }

    const int MOD = 998244353;
    vector<vector<ll>> res = mat_pow(m, n, MOD);

    ll ans = 0;
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k; j++) {
            ans += res[i * k * k + j * k][0];
            ans %= MOD;
        }
    }

    cout << ans << endl;

    //cout << fixed << setprecision(15) << << endl;
    return 0;
}
0