結果

問題 No.840 ほむほむほむら
コンテスト
ユーザー kotamanegi
提出日時 2019-06-14 22:55:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 406 ms / 4,000 ms
コード長 2,776 bytes
コンパイル時間 1,135 ms
コンパイル使用メモリ 111,456 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 12:39:40
合計ジャッジ時間 4,018 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 30000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 998244353LL
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
long long powering(long long now,long long now_go){
	long long ans = 1;
	while (now_go != 0) {
		if (now_go % 2 == 1) {
			ans *= now;
			ans %= MAX_MOD;
		}
		now *= now;
		now %= MAX_MOD;
		now_go /= 2;
	}
	return ans;
}
vector<long long> calc(vector<long long> a, vector<long long> b) {
	long long k = sqrt(a.size());
	vector<long long> ans;
	for (int i = 0; i < k; ++i) {
		for (int q = 0; q < k; ++q) {
			//ans[i][q]を計算する
			long long geko = 0;
			for (int t = 0; t < k; ++t) {
				geko += a[i * k + t] * b[t * k + q];
				geko %= MAX_MOD;
 			}
			ans.push_back(geko);
		}
	}
	return ans;
}
vector<long long> powered(vector<long long> a, long long n) {
	vector<long long> ans = a;
	n--;
	while (n != 0) {
		if (n % 2 == 1) {
			ans = calc(ans, a);
		}
		a = calc(a, a);
		n /= 2;
	}
	return ans;
}
long long inv(long long now) {
	return powering(now, MAX_MOD - 2LL);
}
int main(){
	long long n, k;
	cin >> n >> k;
	//行列構築
	vector<long long> starter;
	REP(i, k*k*k) {
		int now = i;
		int a = now % k;
		now /= k;
		int b = now % k;
		now /= k;
		int c = now % k;
		REP(j, k*k*k) {
			now = j;
			int d = now % k;
			now /= k;
			int e = now % k;
			now /= k;
			int f = now % k;
			//take A
			int ok = 0;
			if ((a + 1) % k == d&&b == e&&c == f) {
				ok++;
			}
			//take B
			if (a == d && (a + b) % k == e && c == f) {
				ok++;
			}
			//take C
			if (a == d && b == e && (b + c) % k == f) {
				ok++;
			}
			starter.push_back(ok);
		}
	}
	vector<long long> ans = powered(starter, n);
	long long final_ans = 0;
	REP(i, k* k* k) {
		int now = i;
		int a = now % k;
		now /= k;
		int b = now % k;
		now /= k;
		int c = now % k;
		REP(j, k * k * k) {
			now = j;
			int d = now % k;
			now /= k;
			int e = now % k;
			now /= k;
			int f = now % k;
			if (d == 0 && e == 0 && f == 0) {
				//候補
				if (c == 0) {
					final_ans += ans[i * k * k * k + j];
					final_ans %= MAX_MOD;
				}
			}
		}
	}
	cout << final_ans << endl;
	return 0;
}
0