線形遷移・行列累乗
固定線形遷移を行列または線形漸化式として巨大回数進める。
この典型を扱う単元: 固定線形遷移を巨大回数進める
検索別名: matrix exponentiation、行列累乗
未知問からこの典型を見つける手掛かり
- 扱う対象
- 巨大な回数
- 漸化式
- 線形遷移
- 行列
- 使う手掛かり
- 二分べき
- 同じ遷移
- 累乗
- 保つ不変量
- 固定行列
- 特性多項式
- 線形
- 求めるもの
- n回後
- 巨大
- 高速化
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC293 E「Geometric Progression」 公式問題主題: 固定線形遷移を巨大回数進める / 主タグ
- ABC256 G「Black and White Stones」 公式問題主題: 固定線形遷移を巨大回数進める / 主タグ
- ABC270 Ex「add 1」 公式問題主題: 確率過程・期待値DP / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC245 Ex「Product Modulo 2」 公式問題主題: 一次合同・CRTで解の類を統合する / 補助タグ
- ABC256 G「Black and White Stones」 公式問題主題: 固定線形遷移を巨大回数進める / 主タグ
- ABC258 Ex「Odd Steps」 公式問題主題: 固定線形遷移を巨大回数進める / 主タグ
- ABC270 Ex「add 1」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC271 G「Access Counter」 公式問題主題: 固定線形遷移を巨大回数進める / 主タグ
- ABC293 E「Geometric Progression」 公式問題主題: 固定線形遷移を巨大回数進める / 主タグ
- ABC299 Ex「Dice Sum Infinity」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC300 Ex「Fibonacci: Revisited」 公式問題主題: Bostan–Mori・有理生成関数の係数抽出 / 補助タグ
- ABC305 G「Banned Substrings」 公式問題主題: 有限状態automatonの構成 / 補助タグ
- ABC429 G「Sum of Pow of Mod of Linear」 公式問題主題: 整数境界と同値区間を正確に分ける / 補助タグ
- ABC458 F「Critical Misread」 公式問題主題: Aho–Corasick / 補助タグ