AIで解説 AtCoder攻略　行列累乗

行列累乗ページの位置づけ

項目	内容
必修度	発展
学習目安	発展
前提	行列・二分累乗
対象問題	4問（推定値あり4問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	0
標準	0〜799	0
標準〜発展	800〜1199	0
発展	1200以上	4
未算出	—	0

状態を行列にまとめ、繰り返し二乗法で巨大な回数の漸化式を処理します。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

行列累乗の見分け方

同じ線形変換を何度も適用する
回数が大きく一回ずつの更新が間に合わない
状態を少数の変数へ閉じ込められる

行列累乗の実装前チェック

行列の各要素が何を表すか固定する
指数0の単位行列を確認する
掛け算の順序と法を小さい回数で検算する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC189 E Rotate and Flip（公式解説）を解きます。回転・反転を3×3の同次座標行列に置き換え、操作を順番に行列の積として保存します。各クエリは保存済み行列を1回適用します。

def multiply(a, b):
    return [[sum(a[i][k] * b[k][j] for k in range(3)) for j in range(3)] for i in range(3)]

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
M = int(input())
identity = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
current = identity
transforms = [identity]

for _ in range(M):
    operation = list(map(int, input().split()))
    kind = operation[0]
    if kind == 1:
        transform = [[0, 1, 0], [-1, 0, 0], [0, 0, 1]]
    elif kind == 2:
        transform = [[0, -1, 0], [1, 0, 0], [0, 0, 1]]
    elif kind == 3:
        p = operation[1]
        transform = [[-1, 0, 2 * p], [0, 1, 0], [0, 0, 1]]
    else:
        p = operation[1]
        transform = [[1, 0, 0], [0, -1, 2 * p], [0, 0, 1]]
    current = multiply(transform, current)
    transforms.append(current)

Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    matrix = transforms[a]
    x, y = points[b - 1]
    print(matrix[0][0] * x + matrix[0][1] * y + matrix[0][2], matrix[1][0] * x + matrix[1][1] * y + matrix[1][2])

行列の積はサイズが固定なのでO(1)、前計算O(M)、各クエリO(1)です。毎回操作を最初から再実行するO(MQ)を避けられます。

行列累乗の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC189 E Rotate and Flip	公式解説	Represent rotations and reflections as affine matrices and answer each query using the composed prefix transform.	1526
ABC199 F Graph Smoothing	公式解説	Express one smoothing step as a linear transition matrix and exponentiate it to K steps.	2065
ABC200 F Minflip Summation	公式解説	Count minimum flips over repeated binary patterns using a small automaton and fast exponentiation of its transition recurrence.	2556
ABC129 F Takahashi’s Basics in Education and Learning	公式解説	連結する数列を桁数ごとの3×3行列にし、繰り返し二乗法で巨大な回数を処理する。	2621