题解

思路

由于 $A,B,C$ 完全对称，只需维护两类方案数：位于 $D$ 的方案数 home，以及位于三个其他顶点的方案总数 away。

一步后，所有 away 方案各有唯一一条边回到 $D$；每个在 $D$ 的方案有三种离开方式，而每个不在 $D$ 的方案有两种走到另一个非 $D$ 顶点的方式。

做法

转移为

$$\begin{pmatrix}home'\\away'\end{pmatrix}= \begin{pmatrix}0&1\\3&2\end{pmatrix} \begin{pmatrix}home\\away\end{pmatrix}.$$

初始向量为 $(1,0)$。对转移矩阵做 $n$ 次方的二进制快速幂，乘初始向量后取 home 分量。

正确性证明

四面体任意两个不同顶点间都有边。位于非 $D$ 顶点的每条路径下一步恰有一种选择回到 $D$，故 home'=away。位于 $D$ 的路径有三种离开方式；位于其他顶点的路径有两种仍留在非 $D$ 集合的方式，故 away'=3home+2away。矩阵准确表示一步转移，从正确初始向量应用 $n$ 次后，home 正是长度为 $n$ 且回到 $D$ 的路径数。

复杂度分析

矩阵大小固定，时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$。

子任务说明

• $n\le12$ 时递归枚举全部路径。
• $n\le10^5$ 时逐步维护四个顶点的方案数。
• 满数据使用二状态矩阵快速幂。