给你若干组有直接关系的两人，求关系最远的两人所隔的关系数。
发现数据范围很小，直接弗洛伊德 \(O\left(TP^3\right)\) 艹过去了。但边权为 \(1\) 可以用广搜做到 \(O\left(TP\left(P+R\right)\right)\)。
一个带权网格图，给定起点和终点，求最短路。其中第一条边、最后一条边以及每个拐点的相邻两条边的权值要算两次。
拆点，用 \(\left(i,j,0/1/2/3/4\right)\) 表示 \((i,j)\) 这个点拆成的五个点。其中 \(0\) 表示上一条边算两次，\(1/2/3/4\) 表示上一条边只算一次，方向是上/下/左/右。
然后无脑连边，自己想一下，我就不说了。
时间复杂度 \(O\left(nm\log nm\right)\)。
大概就是给你一个化学方程式然后配平，有括号。
模拟，对每种化学元素搞个桶，括号用栈处理一下，前缀数字记录下来最后去乘，后缀数字直接找到乘上就是了。
时间复杂度能过。
转化后变成求
令 \(f_i=\sum\limits_{i=1}^n p^i\left(i+1\right)\)。
用矩乘优化
\(\begin{bmatrix}f_{i-1}&p^i\left(i+1\right)&p^i\end{bmatrix}\cdot\begin{bmatrix}1&0&0\\1&p&0\\0&p&p\end{bmatrix}=\begin{bmatrix}f_i&p^{i+1}\left(i+2\right)&p^{i+1}\end{bmatrix}\)
时间复杂度 \(O\left(\log n\right)\)。
原文：https://www.cnblogs.com/May-2nd/p/13849090.html