A – 迷宫
这道题挺好的，让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路，大概的维护方法非常像 Floyd。也没啥好说的，看代码吧。
这道题挺好的，让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路，大概的维护方法非常像 Floyd。也没啥好说的，看代码吧。
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：
这道题的式子跟 Codeforces 一道 F 题是一样的，让我误以为是 BSGS 之类的玩意，最后发现其实算是矩阵乘法的题。
考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的，由于\(k\)很小，所以我们可以考虑计算每一个\(f\)的指数，然后就可以用快速幂来计算这些东西。
首先，这道题是概率和期望分开算的，进行 DP 时实质上是对概率进行 DP。考虑拆位，设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率，那么显然：
\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]
其中，\((1 – dp_b[v])\)为\(v\)为\(0\)的概率，最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。
这道题看了题解之后发现就是一道 sb 题。
考虑将每一列看成一个数，发现如果忽略掉列的操作，这些数仍然满足等差的条件，所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作，那么我们就大力暴力就行了，时间复杂度是\(O(n + m)\)。