yukicoder No.1112 冥界の音楽 - かんプリンの学習記録

問題概要

${T_i\le K}$ かつ ${(T_i,T_{i+1},T_{i+2})=(P_j,Q_j,R_j)}$ となる ${j}$ が存在するような ${1}$ で始まり ${1}$ で終わるような長さ ${N}$ の数列 ${T}$ の数を ${10^9+7}$ で割った余りを求めよ.

${(P_j,Q_j)→(Q_j,R_j)}$ に辺を張ったグラフの隣接行列を作る.
蟻本とかにも書いてあるように, この行列を ${n}$ 乗した行列の ${(i,j)}$ 成分は「頂点 ${i}$ から頂点 ${j}$ まで ${n}$ 本の辺を通って行く場合の数」となる.

今回の場合頂点が ${(T_i,T_{i+1})}$ であるので ${T}$ の長さが ${N}$ であることを考えると隣接行列を ${N-2}$ 乗すればいい.(サンプルとか考えるとわかる).

答えは行列の ${(1,x)→(y,1)}$ となる成分の合計が答えとなる.

これ系の無向グラフの三角形の数えるやつグラフ理論で習って印象に残ってたから解けた.