結果

問題 No.840 ほむほむほむら
ユーザー 双六双六
提出日時 2020-07-15 22:26:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 946 ms / 4,000 ms
コード長 1,446 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 77,440 KB
最終ジャッジ日時 2024-05-02 04:20:10
合計ジャッジ時間 7,737 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
61,952 KB
testcase_01 AC 65 ms
63,232 KB
testcase_02 AC 83 ms
65,024 KB
testcase_03 AC 185 ms
72,320 KB
testcase_04 AC 58 ms
61,824 KB
testcase_05 AC 58 ms
62,080 KB
testcase_06 AC 63 ms
63,744 KB
testcase_07 AC 102 ms
67,968 KB
testcase_08 AC 290 ms
76,672 KB
testcase_09 AC 64 ms
63,360 KB
testcase_10 AC 59 ms
62,336 KB
testcase_11 AC 67 ms
64,768 KB
testcase_12 AC 129 ms
71,808 KB
testcase_13 AC 636 ms
77,056 KB
testcase_14 AC 142 ms
73,472 KB
testcase_15 AC 60 ms
62,976 KB
testcase_16 AC 83 ms
66,176 KB
testcase_17 AC 209 ms
76,160 KB
testcase_18 AC 797 ms
76,928 KB
testcase_19 AC 946 ms
77,056 KB
testcase_20 AC 55 ms
60,672 KB
testcase_21 AC 60 ms
61,952 KB
testcase_22 AC 73 ms
64,256 KB
testcase_23 AC 913 ms
77,056 KB
testcase_24 AC 76 ms
67,072 KB
testcase_25 AC 57 ms
61,184 KB
testcase_26 AC 82 ms
65,024 KB
testcase_27 AC 908 ms
77,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353

def getlist():
	return list(map(int, input().split()))

#A*B
def mul(A, B):
	C = [[0] * len(B[0]) for i in range(len(A))]
	for i in range(len(A)):
		for k in range(len(B)):
			for j in range(len(B[0])):
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
	return C

#A**n 繰り返し二乗法の要領で計算する N:行列の縦横の大きさ
def matrixPow(A, n, N):
	#B:単位行列 演算の種類によって初期化方法を変える必要もある
	B = [[0] * N for i in range(N)]
	for i in range(N):
		B[i][i] = 1

	while n > 0:
		if n & 1 == 1:
			B = mul(A, B)
		A = mul(A, A)
		n = n >> 1

	return B

#処理内容
def main():
	N, K = getlist()
	Det = [[0] * (K ** 3) for i in range(K ** 3)]
	for x in range(K):
		for y in range(K):
			for z in range(K):
				itr = x + y * K + z * (K ** 2)
				x_new = (x + 1) % K
				newind1 = (x + 1) % K + y * K + z * (K ** 2)
				newind2 = x + (y + x) % K * K + z * (K ** 2)
				newind3 = x + y * K + (z + y) % K * (K ** 2)
				Det[newind1][itr] += 1
				Det[newind2][itr] += 1
				Det[newind3][itr] += 1

	B = matrixPow(Det, N, K ** 3)
	# print(Det)

	start = [[0] for i in range(K ** 3)]
	start[0][0] = 1
	ans_pre = mul(B, start)
	# print(ans_pre)
	ans = 0
	for i in range(K ** 2):
		ans += ans_pre[i][0]

	ans %= mod
	print(ans)


if __name__ == '__main__':
	main()
0