没有限制怎么做？邻接矩阵 \(k\) 次方。
有限制？
设 \(A\) 为邻接矩阵， \(I\) 为单位矩阵，\(deg_u\) 为 \(u\) 的度数，步数为 \(k\) 是的答案矩阵 \(R_k\)，即 \(R_k[u][v]\) 应该表示 \(u\to v\) 长度为 \(k\) 的合法路径条数。
如果我们知道了 \(R_1,R_2,\dots,R_{k-1}\)，我们想求出 \(R_k\)。没有限制的话 \(R_k=R_{k-1}\times A\)。考虑由这个结果进行去重得到正确的矩阵。
考虑不合法的本质是啥。
由于前面的矩阵保证了答案正确，那么不合法一定出现在最后两步。即最后走的两步一定是 \((u\to v)\to x\to v\)。那么每条不合法路径都是 \(R_{k-2}\) 中的一条路径往外走一步再走回来。
设 \(\bold{T}=R_{k-1}\times A\)。
所以矩阵 \(\bold{T}\) 中每个位置 \(\bold{T}[i][j]\) 中不合法的路径数量应该是 \(R_{k-2}[i][j]\times (deg_j-1)\)。这个减 1 是因为来回跳两步的时候第一步不能走 \((u\to v)\to u\)，即第一步 \(u\) 是不能走的（因为相当于 \(R_{k-1}\) 里都是是合法路径，第一步走 \(u\) 不合法）。
但是当 \(k=2\) 的时候又不能减 1，因为 \(R_{k-2}=R_{0}\)，此时不存在上述的 \(u\)。此时特殊处理即可。
忽略 \(k=2\)，设矩阵 \(E\)，\(E[i][i]=deg_i-1\)， \(E[i][j](i\not=j)=0\)，易得 \((R_{k-2}\times E)[i][j]\) 的结果就是 \(R_{k-2}[i][j]\times (deg_j-1)\)
那么 \(R_k=R_{k-1}\times A-R_{k-2}\times E\)。得到了 \(O(n^3k)\) 的做法。
考虑把矩阵压进矩阵进行优化。
\[\begin{bmatrix}R_{k-1}& R_{k-2}\end{bmatrix}\begin{bmatrix}A& I\\-E & 0\end{bmatrix}=\begin{bmatrix}R_{k}& R_{k-1}\end{bmatrix} \]\(0\) 表示全是 0， \(-E\) 是 \(E\) 中每个元素都变成其相反数。
提前计算出 \(R_0,R_1,R_2\)，那么
\[\begin{bmatrix}R_{2}& R_{1}\end{bmatrix}\begin{bmatrix}A& I\\-E & 0\end{bmatrix}^{k-2}=\begin{bmatrix}R_{k}& R_{k-1}\end{bmatrix} \]由矩阵乘法可得直接把矩阵拆开是对的，即把 \(\begin{bmatrix}A& I\\-E & 0\end{bmatrix}\) 拆成 \(2n\times 2n\) 的矩阵是合理的。
复杂度 \(O(8n^3\log k)\)。
标签：CF1662C,end,矩阵,begin,times,bmatrix,合法,Trip,European From： https://www.cnblogs.com/jimmywang/p/17567310.html