結果

問題 No.3584 Camouflage Mole
コンテスト
ユーザー 回転
提出日時 2026-07-11 15:27:23
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 163 ms / 2,000 ms
+ 763µs
コード長 3,009 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 242 ms
コンパイル使用メモリ 96,108 KB
実行使用メモリ 90,880 KB
最終ジャッジ日時 2026-07-11 15:27:33
合計ジャッジ時間 8,394 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from typing import Callable, TypeVar
T = TypeVar("T")

class MatrixCalculator:
    plus: Callable[[T, T], T]
    e_plus: T
    times: Callable[[T, T], T]
    e_times: T

    def __init__(
        self,
        plus: Callable[[T, T], T],
        e_plus: T,
        times: Callable[[T, T], T],
        e_times: T,
    ):
        self.plus = plus
        self.e_plus = e_plus
        self.times = times
        self.e_times = e_times

    def add(self, A: list[list[T]], B: list[list[T]]) -> list[list[T]]:
        """A + B を計算する"""
        h_a, w_a = len(A), len(A[0])
        h_b, w_b = len(B), len(B[0])

        assert h_a == h_b and w_a == w_b

        res = self._zero(h_a, w_a)
        
        # 関数呼び出しのオーバーヘッドを削減
        plus = self.plus

        for i in range(h_a):
            for j in range(w_a):
                # 修正: 組み込みの + ではなく self.plus を使用する
                res[i][j] = plus(A[i][j], B[i][j])

        return res

    def mul(self, A: list[list[T]], B: list[list[T]]) -> list[list[T]]:
        """A * B を計算する"""
        h_a, w_a = len(A), len(A[0])
        h_b, w_b = len(B), len(B[0])

        assert w_a == h_b

        res = self._zero(h_a, w_b)

        # ローカル変数に退避して関数呼び出しを高速化
        plus = self.plus
        times = self.times
        e_plus = self.e_plus

        # i-k-j ループに変更し、内側のループを軽くする
        for i in range(h_a):
            row_res = res[i]
            row_a = A[i]
            for k in range(w_a):
                val_a = row_a[k]
                # A[i][k] が加法単位元（0など）なら掛け算しても0なのでスキップ (定数倍高速化)
                if val_a == e_plus:
                    continue
                row_b = B[k]
                for j in range(w_b):
                    row_res[j] = plus(row_res[j], times(val_a, row_b[j]))

        return res

    def power(self, A: list[list[T]], e: int) -> list[list[T]]:
        """A**e を計算する"""
        n, m = len(A), len(A[0])

        assert n == m

        res = self._identity(n)
        base = A

        # 下からの繰り返し二乗法（簡素で書きやすい定石）
        while e > 0:
            if e & 1:
                res = self.mul(res, base)
            base = self.mul(base, base)
            e >>= 1

        return res

    def _zero(self, h: int, w: int):
        """h 行 w 列の零行列"""
        return [[self.e_plus for _ in range(w)] for _ in range(h)]

    def _identity(self, n: int):
        """n 次単位行列"""
        return [
            [self.e_times if i == j else self.e_plus for j in range(n)]
            for i in range(n)
        ]

MOD = 998244353
N = int(input())

A = [
    [26,1,0,0,0],
    [0,26,1,0,0],
    [0,0,26,1,0],
    [0,0,0,26,1],
    [0,0,0,0,26]
    ]

MC = MatrixCalculator(lambda x,y:(x+y) % MOD, 0, lambda x,y:x*y % MOD, 1)
print(MC.power(A, N)[0][4])
0