矩阵相关 \(Trick\) 合集

认知

矩阵乘法的 \(n\) 种理解方式。

• 定义式：\(C_{i,k}=\sum A_{i,j}\times B_{k,j}\) $\times $ 满足交换律，结合律，\(+\) 满足交换律，$\times $ 对 \(+\) 满足分配

  常见形式：\((+,\times ),(\min,+),(\max,+),(|,\&)\)

• 概念式：利用结合律对一个线性操作的叠加进行快速运算

• 动规式：分层的状态转移，每一层的转移规则改写为定义式

  • \((+,\times )\) 方案数
  • \((\min,+)\) 最小化
  • \((\max,+)\) 最大化
  • \((|,\&)\) 可行性

• 图论式：分层图的 “行走”

  \(A^k(i,j)\) \(i\to j\) 行走 \(k\) 步结果

  借助运算记录信息（本质是动归的图上解释）

• 区间式：在某一前提下所进行的运算式

  是不借助动归式直接写转移矩阵的本质。

  \(A_{i,j}\) 可以理解为在有前提 \(i\) 的情况下达到条件 \(j\) 的信息。

  进行合并的时候，有同样的前提，相当于 \(A_{i,j}\times B_{j,k}\) 是这个转移的中间步骤。

• 断点式：定义式中的 \(j\) 的"拼凑决策"中枚举断点的一步

应用

• 维护一维向量（线性递推？）

  有常见的形式如：

  • 线性递推，例 \(Fib_{n}=Fib_{n-1}+Fib_{n-2}\implies [Fib_{n-1},Fib_n]\times A\to [Fib_n,Fib_{n+1}]\)。P5768 构造转移矩阵。

  • 操作轴的线性变换，例维护向量 \([a,b,c,1]\)，支持交换某些位置，某些位置加，某些位置乘……（将操作改写为转移矩阵），如 THUSCH2017 大魔法师，CF1458C

    可以理解为上一个时刻的状态过渡到当前时刻。

  • 时间轴的线性变换，例维护某种特定行走策略下某一时刻的某些信息 如 CF593E

  • 决策树上线性变换，例维护相关的单点决策合并到整体决策的决策方案数，可行性，最优解等信息，如 CF1995E2

• 维护