[CF1662C] European Trip

如果没有不能相邻两次走同一条边的限制，可以直接矩阵快速幂。对于这样的限制，整体地考虑所有路径，进行容斥亦不现实。

所以回归矩阵乘法做图上路径计数的本质——动态规划。

设 $f_t(i,j)$ 为 $i\to j$ 长为 $t$，且不走回头路的路径数量，那么对于 $t\ge3$ 有递推式

$$\displaylines{f_t(i,j)=\sum_k f_{t-1}(i,k)f(k,j)-(d_j-1)f_{t-2}(i,j) }$$

其中 $d_i$ 等于 $i$ 的度。那么令矩阵 $G_t$ 第 $i$ 行第 $j$ 列为 $f_t(i,j)$，$G_1=G$ 即为原图邻接矩阵，上式等同于

$$\displaylines{G_t=G_{t-1}G-(D-I)G_{t-2} }$$

其中 $D=\mathrm{diag}(d_1,d_2,\cdots,d_n)$。不难发现上式可以矩阵加速：

$$\displaylines{\begin{bmatrix}O&I\\I-D&G\end{bmatrix} \begin{bmatrix}G_{t-2}\\G_{t-1}\end{bmatrix} =\begin{bmatrix}G_{t-1}\\G\end{bmatrix} }$$

矩阵套矩阵，喵喵题。