CF718C Sasha and Array
Codeforces Luogu 分析 考虑怎么用矩阵求出斐波那契数列的。有 为了方便，下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。 考虑使用线段树维护。每个叶子节点维护一个矩阵：若该位置的值为 $i$ ，则维护的矩阵为 $Q^{i-1}$ 。 注意到矩阵乘法是满足分配律的，那么我们只需要求 $[l,r]$ 内所有维护的矩阵的...
Codeforces Luogu 分析 考虑怎么用矩阵求出斐波那契数列的。有 为了方便，下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。 考虑使用线段树维护。每个叶子节点维护一个矩阵：若该位置的值为 $i$ ，则维护的矩阵为 $Q^{i-1}$ 。 注意到矩阵乘法是满足分配律的，那么我们只需要求 $[l,r]$ 内所有维护的矩阵的...
Luogu 分析 由熟知结论，邻接矩阵的 $k$ 次幂中 $(u, v)$ 上的数表示 $u\to v$ 恰好走 $k$ 步的方案数。 然而本题有一个不动和自爆的问题。 不动的话，相当于走自环；自爆的话，减一个 $0$ 号节点，$0 \sim n$ 都向 $0$ 连一条边即可。这样子保证了自爆后就没有后继了。 代码 #include <bits/stdc++.h> #define...