概要
円環上の DP が問題は、DP を行列積で書くことで行列のトレースになることが多いのですが、立て続けに 2 問お見かけしたため共有です。
両方とも辺被覆の話題でしたが、たまたまでしょうかね。
本文
ABC 247 F - Cards
長さ $n ( \ge 1)$ のサイクルグラフの辺被覆の個数
$$ \mathop{\mathrm{Tr}} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} ^ n $$
ABC 251 E - Takahashi and Animals
重み $A _ 0, A _ 1, \dots, A _ { n - 1 }$ の辺を持つサイクルグラフの、最小重み辺被覆
$$ \mathop{\mathrm{Tr}} _ { \oplus, \odot } \bigodot _ { 0 \le i \lt N } \begin{pmatrix} \infty & 0 \\ A _ i & A _ i \end{pmatrix} $$
（ただし演算は $\mathrm{min}, +$）
